2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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? $\endgroup$ – Batominovski Dec 14 '18 at 14:18
  • $\begingroup$ @Snookie how would one approach if N was not a multiple of four?? $\endgroup$ – itachi101 Dec 14 '18 at 18:55
  • $\begingroup$ @Batominovski can you help me out $\endgroup$ – itachi101 Dec 15 '18 at 13:51
  • 1
    $\begingroup$ @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$. $\endgroup$ – user614671 Dec 15 '18 at 18:20
  • 1
    $\begingroup$ @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. $\endgroup$ – Batominovski Dec 15 '18 at 22:34
0
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.