# Find elements from xor relations

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

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$$.

• Here is a comment by @tech001 who doesn't have enough reputation to make a comment. Additional condition: for each index $i$, $i$ may appear in all questions in total at most $3$ times. What to do if number of positive integers are not a multiple of $4$, keeping in mind the above constraint because if i use this $a_n=b_n⊕a_{n+1}⊕a_{n+2}$ then the number of time a index is used becomes more than three? – Batominovski Dec 14 '18 at 14:18
• @Snookie how would one approach if N was not a multiple of four?? – itachi101 Dec 14 '18 at 18:55
• @Batominovski can you help me out – itachi101 Dec 15 '18 at 13:51
• @itachi101 I don't have the answer yet. But your condition implies that each index $i$ must appear exactly three times. So the answer depends on whether we can construct a non-singular $n\times n$ matrix $A$ with entries in $\Bbb{Z}/2\Bbb{Z}=\{0,1\}$ such that each row of $A$ contains exactly three $1$, and each column of $A$ contains exactly three $1$. – user614671 Dec 15 '18 at 18:20
• @itachi101 I think you are confused. Snookie gave a complete answer (see the end of his answer). But of course, if you are talking about the additional condition by tech001 (that requires that each index $i$ is asked by Bob at most three times), then I have provided an answer to that. – Batominovski Dec 15 '18 at 22:34

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.

• @tech001 Here is a solution to your modification of the problem. – Batominovski Dec 15 '18 at 22:17