Encuentra elementos de relaciones xor

Question

Alice y Bob están jugando un juego. Alice tiene una secuencia de enteros positivos $$a_1,a_2, \ldots, a_N;$$ Bob should find the values of all elements of this sequence. Bob may ask Alice at most $N$ questions. In each question, Bob tells Alice $3$ distinct indices $i$, $j$, and $k$, y Alicia responde con un número entero $$a_i⊕a_j⊕a_k$$ ($⊕$ denota la operación XOR bit a bit).

Cómo abordar esto? Pensé acerca de cómo calcular xor consultas consecutivas índices ($3$ índices en una hora) y, a continuación, proceder, pero que eso no me ayuda.

Ejemplo

a1^a2^a3=v1

a2^a3^a4=v2

... y así sucesivamente

Dado N>=8

Answer 1

Esta es una respuesta parcial. Véase más abajo para una completa estrategia ganadora para Bob. Si $4$ divide $N$, entonces Bob puede ganar el juego. Puedo demostrar demostrando que, Bob puede encontrar $4$ números usando sólo $4$ pasos, reduciendo $N$ a $N-4$.

La idea es la siguiente. Bob le pregunta por los siguientes índices:

• $(i,j,k)=(N-1,N-2,N-3)$,

• $(i,j,k)=(N,N-2,N-3)$,

• $(i,j,k)=(N,N-1,N-3)$, y

• $(i,j,k)=(N,N-1,N-2)$.

Supongamos que las respuestas por Alice se $b_N,b_{N-1},b_{N-2},b_{N-3}$, respectivamente. Entonces, Bob conoce a los siguientes números: $$a_N=b_{N-1}\oplus b_{N-2}\oplus b_{N-3},$$ $$a_{N-1}=b_N\oplus b_{N-2}\oplus b_{N-3},$$ $$a_{N-2}=b_N\oplus b_{N-1}\oplus b_{N-3},$$ y $$a_{N-3}=b_N\oplus b_{N-1}\oplus b_{N-3}.$$

---

Oh, snap! El resto es fácil. Una vez que Bob sabe $a_N$, $a_{N-1}$, $\ldots$, $a_{n+1}$, entonces Bob puede encontrar $a_{n}$ en un solo paso pidiendo $(i,j,k)=(n+2,n+1,n)$. Entonces, Alice devuelve $b_{n}$, lo que Bob puede deducir $a_{n}$a través de $$a_n=b_n\oplus a_{n+1}\oplus a_{n+2}.$$ Por lo tanto, Bob puede ganar si y sólo si $N\geq 4$.

Answer 2

Esta es una respuesta a tech001 la modificación del problema (ver comentarios bajo Snookie la respuesta). Es decir, para cada índice $i\in\{1,2,\ldots,N\}$, Bob puede pedirle a Alice en la mayoría de las veces. Snookie la respuesta da una indicación de cómo reducir el $N$ a $N-4$. Si $4$ divide $N$, entonces hemos terminado. Por lo tanto, es suficiente para demostrar que la tarea se puede hacer para $N=5$, $N=6$, e $N=7$.

Para $N=5$, Bob le pregunta acerca de las siguientes tripletas $(i,j,k)$:

• $(1,2,3)$ para que Alicia se vuelve $b_1$,
• $(1,3,4)$ para que Alicia se vuelve $b_2$,
• $(1,4,5)$ para que Alicia se vuelve $b_3$,
• $(2,3,5)$ para que Alicia se vuelve $b_4$, y
• $(2,4,5)$ para que Alicia se vuelve $b_5$.

A continuación, $$a_1=b_2\oplus b_4\oplus b_5\,,$$ $$a_2=b_2\oplus b_3\oplus b_4\,,$$ $$a_3=b_1\oplus b_3\oplus b_5\,,$$ $$a_4=b_1\oplus b_3\oplus b_4\,,$$ y $$a_5=b_1\oplus b_2\oplus b_5\,.$$

Para $N=6$, Bob le pregunta acerca de las siguientes tripletas $(i,j,k)$:

• $(1,2,3)$ para que Alicia se vuelve $b_1$,
• $(1,4,5)$ para que Alicia se vuelve $b_2$,
• $(1,4,6)$ para que Alicia se vuelve $b_3$,
• $(2,3,4)$ para que Alicia se vuelve $b_4$,
• $(2,5,6)$ para que Alicia se vuelve $b_5$, y
• $(3,5,6)$ para que Alicia se vuelve $b_6$.

A continuación, $$a_1=b_1\oplus b_5\oplus b_6\,,$$ $$a_2=b_2\oplus b_3\oplus b_5\,,$$ $$a_3=b_2\oplus b_3\oplus b_6\,,$$ $$a_4=b_4\oplus b_5\oplus b_6\,,$$ $$a_5=b_1\oplus b_2\oplus b_4\,,$$ y $$a_6=b_1\oplus b_3\oplus b_4\,.$$

Para $N=7$, Bob le pregunta acerca de las siguientes tripletas $(i,j,k)$:

• $(1,3,5)$ para que Alicia se vuelve $b_1$,
• $(1,3,6)$ para que Alicia se vuelve $b_2$,
• $(1,4,6)$ para que Alicia se vuelve $b_3$,
• $(2,4,6)$ para que Alicia se vuelve $b_4$,
• $(2,4,7)$ para que Alicia se vuelve $b_5$,
• $(2,5,7)$ para que Alicia se vuelve $b_6$, y
• $(3,5,7)$ para que Alicia se vuelve $b_7$.

A continuación, $$a_1=b_1\oplus b_2 \oplus b_3 \oplus b_5\oplus b_6\,,$$ $$a_2=b_1\oplus b_2 \oplus b_4 \oplus b_5\oplus b_6\,,$$ $$a_3=b_1\oplus b_2 \oplus b_4\oplus b_5\oplus b_7\,,$$ $$a_4=b_1\oplus b_3\oplus b_4\oplus b_5\oplus b_7\,,$$ $$a_5=b_1\oplus b_3\oplus b_4 \oplus b_6 \oplus b_7\,,$$ $$a_6=b_2\oplus b_3\oplus b_4 \oplus b_6 \oplus b_7\,,$$ y $$a_7=b_2\oplus b_3\oplus b_5\oplus b_6\oplus b_7\,.$$ El caso de $N=7$ se extrae de Federico's respuesta aquí.