2

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

itachi101
  • 21

2 Answers2

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

  • 1
    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
  • 1
    @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$. –  Dec 15 '18 at 18:20
  • @Snookie Thanks to your comment, I found an answer to this modified problem. – Batominovski Dec 15 '18 at 21:07
  • 1
    @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
0

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.

Batominovski
  • 49,629