Let $T$ be the set of ordered triples $(x,y,z)$, where $x,y,z$ are integers with $0\leq x,y,z\leq9$. Players $A$ and $B$ play the following guessing game. Player $A$ chooses a triple $(x,y,z)$ in $T$, and Player $B$ has to discover $A$'s triple in as few moves as possible. A move consists of the following: $B$ gives $A$ a triple $(a,b,c)$ in $T$, and $A$ replies by giving $B$ the number $\left|x+y-a-b\right |+\left|y+z-b-c\right|+\left|z+x-c-a\right|$. Find the minimum number of moves that $B$ needs to be sure of determining $A$'s triple.
Please post your solutions. This is just a solution template to write up your solutions in a nice way and formatted in LaTeX. But maybe your solution is so well written that this is not required finally. For more information and instructions regarding the ISL/ILL problems please look here: introduction for the IMO ShortList/LongList project and regardingsolutions
Easy to show that two moves can't be enough. In the fact, $ A=\left|x+y-a-b\right |+\left|y+z-b-c\right|+\left|z+x-c-a\right|$ is an even integer and $ 0\le A\le 54$, so there are 28 possibilities for A. If B only perform two moves, the number of possibilities of outcome that we receive is at most 28^2=784<1000, which is a contradiction (because T has 1000 element).
Our task now is to show that three moves are enough.
In the first move, we choose (x,y,z)=(0,0,0), then we know the value of sum S=x+y+z
Clearly $ 0\le S\le 27$, but we should assume $ 0\le S\le 13$ because if $ S\ge 14$, B will ask $ (9 - a),(9 - b),(9 - c)$ instead of $ (a,b,c)$
We divides into two cases:
$ S\le 9$,
Choose (a,b,c)=(9,0,0), we now know the value of x
Choose (a,b,c)=(0,9,0), we know the value of y, hence the value of z.
$ 9 < S\le 13$,
Choose (a,b,c)=(9,S-9,0), then $ S' = 2z$ if $ x + z\ge 9$ and $ S' = 9 - x$ if $ x + z < 9$
If $ 2S - S'\le 18$, choose (a,b,c)=(S-k,0,k) where $ k = \frac {S'}{2}$
If $ 2S - S' > 18$, choose (a,b,c)=(9,S-k-9,k) where $ k = \frac {S'}{2}$
is this right?
suppose that $ B $ can find the triple in $ 2 $ moves.
then from $ 2 $ steps $ B $ obtains a sistem of three variables ( $ x+y,y+z,z+x $ ) and only two equations. so he cannot find the triple of variables which implies that he cannot find the initial triple.
mr.danh wrote:
Our task now is to show that three moves are enough.
[...]
$ 9 < S\le 13$,
Choose (a,b,c)=(9,S-9,0), then $ S' = 2z$ if $ x + z\ge 9$ and $ S' = 9 - x$ if $ x + z < 9$
If $ 2S - S'\le 18$, choose (a,b,c)=(S-k,0,k) where $ k = \frac {S'}{2}$
If $ 2S - S' > 18$, choose (a,b,c)=(9,S-k-9,k) where $ k = \frac {S'}{2}$
I have a slightly different method for this part.
Let $N = 9$. Again, we first use $(0,0,0)$ to find $S = x+y+z$, and WLOG assume $S\le 3N/2$. We will repeatedly use the fact that moves $(a,b,c)$ with $a+b+c = S$ give us $\sum |y+z-b-c| = \sum |x-a|$.
Case 1: $S\le N$. Then $(S,0,0)$ and $(0,S,0)$ yield $(S-x)+y+z = 2(S-x)$ and $2(S-y)$, respectively, and we can finish with $z = S - x - y$.
Case 2: $N+1\le S\le 3N/2$. To keep things simple, we take $(S-N,0,N)$ to get $|S-N-x|+y+(N-z) = 2T$. If $x\le S-N$, then $T = y$ and $z = S-x-y \in [N-T,S-T]$. If $x\ge S-N$, then we similarly find $T = N-z$ and $y = S-x-z\in [S-(2N-T),T]$.
In particular, the inequalities $S-(2N-T)\le y\le T$ and $N-T\le z\le S-T$ hold regardless of the value of $x$. If $T\le S-N$, then we may take $(0,S-N,N)$ to find $x+(S-N-y)+(N-z) = 2x$; similarly, if $N-T\ge S-N$, $(N,0,S-N)$ yields $(N-x)+y+(z-[S-N]) = 2(N-x)$. Either way, we can use $x$ to deduce $y$ and $z$ from the previous paragraph.
Now suppose $T \ge S-N, 2N-S$; then $1\le S-N \le S-T\le N$ allows us to take $(0,T,S-T)$ to find $x+(T-y)+(S-T-z) = 2x$, so we're done here as well.
Comment. I wrote Case 2 focusing on motivation rather than brevity; some steps are unnecessary, but IMO still help illustrate the flexibility of the construction.
Creds to Adit Vishnu:
It can be achieved in 3 moves:
Take (a,b,c) = (0,0,0). From this, we get 2x+2y+2z, from which we can acquire x+y+z = S.
Take (a,b,c) = (S,0,0). From this, we get 2(y+z), from which we can acquire x.
Take (a,b,c) = (0,S,0). From this, we can get 2(x+z), from which we can acquire y.
We can then get z and B can give the triple (x,y,z).
To prove minimality, or that it cannot always be achieved in 2 moves or less, the first move would get 28 possible values and the second would give 28 possible values as well, for a total of 784 combinations. (The value of each move must always be even). But there are 1000 total possible values for x, y, z, so there would have to be a combination of values from the two moves that would generate at least two possible values of x, y, z, contradiction.
There are a total of $1000$ triples. Note that $A$'s reply will be even, and that it will be between $0$ and $54$, so there are a total of $28$ different replies. Therefore, there exists at least one pair of replies that matches at least two triples, so two is not enough.
Three is enough. If $B$ asks $(0,0,0)$ the reply will be $2x+2y+2z$ so he knows the sum. If the sum is at most $9$, asking $(9,0,0)$ will get the reply $|x+y-9|+|y+z-0|+|z+x-9|=18-2x$. And similarly we can find $y$. On the other hand, if the sum is at least $18$ we can ask $(0,9,9)$ to find $x$ and similarly find $y$. In both cases, we can find $x,y,z$ in three moves.
If $10\le x+y+z\le 17$ then first ask $(9,x+y+z-9,0)$ then we have \[z+|-x+9|+|x+z-9|=z+9-x+|x+z-9|\]which is either $2z$ when $x+z\ge 9$ or $18-2x$ when $x+z<9$. Let our answer be $2a$.
Then, if $s-a\le 9$, we can ask $(s-k,0,k)$ to get
\[|a-z|+|y+z-a|+|y|.\]If $a$ is $z$ then we are done since we found $y$ and therefore we found $x+z$. If $a$ is $9-x$ we still have work to do. We get the result $|y-s+9|+s-9+|y|$. We do get $2|y|$ unless $y \le s-9$ in which case we get $2s-18$. Thus, if we get $2s-18$ then we know that $y \le s-9=x+y+z-9$ so $x+y\ge 9$, contradiction. If $s-a>9$ then pick $(9,s-a-9,a)$ for a similar result.
sad
Let's prove that 3 moves are enough. Set $(a,b,c)=(0,0,0)$, then we can find the sum $S=x+y+z$.
Now, we have three cases.
First case: $S \leq 9$. Then we can choose $(a,b,c)=(9,0,0)$ to find $x$ and similarly we can find $z$ or $y$.
$|x+y-9|+|y+z|+|z+x-9|=9-x-y+y+z+9-z-x=18-2x$.
Second case: $10 \leq S \leq 17$, we can set $(a,b,c)=(x+y+z-9,0,18)$. To find $z$, similarly we can find $y$.
$|x+y-x-y-z+9|+|y+z-18|+|x+z-x-y-z+9-18|=36-2z$.
Third case: $18 \leq S \leq 27$. Then setting $(a,b,c)=(9,9,0)$, we can find $z$. So on..
$|x+y-18|+|y+z-9|+|z+x-9|=18-x-y+y+z-9+z+x-9=2z$. $\blacksquare$
Same solution as everyone else, but I think it's more natural to think about this problem geometrically. The idea is that for every guess $(a,b,c)$ by $B$, $A$ returns the taxicab distance between $(x+y,y+z,z+x)$ and $(a+b, b+c, c+a)$. Moreover, one can deduce $(x,y,z)$ from $(x+y,y+z,z+x)$.
Now, replace the taxicab metric with the standard Euclidean metric. Playing around for a bit, one finds that three guesses is sufficient, and that the main way to avoid ambiguity is to guess "near the boundary" of the cube given by $0\le x+y, y+z, z+x \le 18$. This intuition translates back pretty naturally to get us the algorithm.
Oh, and I guessed the answer was $3$ from the "obvious" code bound