Find elements from xor relations

Question

Alice and Bob are playing a game. Alice has a sequence of positive integers $$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$, and Alice responds with an integer $$a_i⊕a_j⊕a_k$$ ($⊕$ denotes bitwise XOR).

How to approach this? I thought about calculating xor queries for consecutive indices ($3$ indices at a time) and then proceed but that did not help me.

Example

a1^a2^a3=v1

a2^a3^a4=v2

… and so on

Given N>=8

Answer 1

This is a partial answer. See below for a complete winning strategy for Bob. If $4$ divides $N$, then Bob can win the game. I prove by showing that, Bob can find $4$ numbers by using only $4$ steps, thereby reducing $N$ to $N-4$.

The idea is as follows. Bob asks for the followings indices:

• $(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)$, and

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

Suppose that the answers by Alice are $b_N,b_{N-1},b_{N-2},b_{N-3}$, respectively. Then, Bob knows the following numbers: $$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},$$ and $$a_{N-3}=b_N\oplus b_{N-1}\oplus b_{N-3}.$$

---

Oh, snap! The rest is easy. Once Bob knows $a_N$, $a_{N-1}$, $\ldots$, $a_{n+1}$, then Bob can find $a_{n}$ in one step by asking for $(i,j,k)=(n+2,n+1,n)$. Then, Alice returns some $b_{n}$, which Bob can deduce $a_{n}$ via $$a_n=b_n\oplus a_{n+1}\oplus a_{n+2}.$$ Thus, Bob can win if and only if $N\geq 4$.

Answer 2

This is an answer to tech001's modification of the problem (see comments under Snookie's answer). That is, for each index $i\in\{1,2,\ldots,N\}$, Bob can ask Alice about it at most thrice. Snookie's answer gives an indication how to reduce $N$ to $N-4$. If $4$ divides $N$, then we are done. Therefore, it suffices to prove that the task can be done for $N=5$, $N=6$, and $N=7$.

For $N=5$, Bob asks about the following triples $(i,j,k)$:

• $(1,2,3)$ for which Alice returns $b_1$,
• $(1,3,4)$ for which Alice returns $b_2$,
• $(1,4,5)$ for which Alice returns $b_3$,
• $(2,3,5)$ for which Alice returns $b_4$, and
• $(2,4,5)$ for which Alice returns $b_5$.

Then, $$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\,,$$ and $$a_5=b_1\oplus b_2\oplus b_5\,.$$

For $N=6$, Bob asks about the following triples $(i,j,k)$:

• $(1,2,3)$ for which Alice returns $b_1$,
• $(1,4,5)$ for which Alice returns $b_2$,
• $(1,4,6)$ for which Alice returns $b_3$,
• $(2,3,4)$ for which Alice returns $b_4$,
• $(2,5,6)$ for which Alice returns $b_5$, and
• $(3,5,6)$ for which Alice returns $b_6$.

Then, $$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\,,$$ and $$a_6=b_1\oplus b_3\oplus b_4\,.$$

For $N=7$, Bob asks about the following triples $(i,j,k)$:

• $(1,3,5)$ for which Alice returns $b_1$,
• $(1,3,6)$ for which Alice returns $b_2$,
• $(1,4,6)$ for which Alice returns $b_3$,
• $(2,4,6)$ for which Alice returns $b_4$,
• $(2,4,7)$ for which Alice returns $b_5$,
• $(2,5,7)$ for which Alice returns $b_6$, and
• $(3,5,7)$ for which Alice returns $b_7$.

Then, $$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\,,$$ and $$a_7=b_2\oplus b_3\oplus b_5\oplus b_6\oplus b_7\,.$$ The case $N=7$ is extracted from Federico's answer here.