IMO 2002 SL C4

Origin: BUL | Category: Combinatorics

Problem

Let T be the set of ordered triples (x, y, z), where x, y, z are integers with 0 \leqx, 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 |x + y −a −b| + |y+ z −b −c| + |z+ x −c −a|. Find the minimum number of moves that B needs to be sure of determining A’s triple.

Solution

Two moves are not sufficient. Indeed, the answer to each move is an even number between 0 and 54, so the answer takes at most 28 distinct values. Consequently, two moves give at most 282 = 784 distinct outcomes, which is less than 103 = 1000. We now show that three moves are sufficient. With the first move (0, 0, 0), we get the reply 2(x + y + z), so we now know the value of s = x + y + z. Now there are several cases: (i) s \leq9. Then we ask (9, 0, 0) as the second move and get (9 −x −y) + (9 −x −z) + (y + z) = 18 −2x, so we come to know x. Asking (0, 9, 0) we obtain y, which is enough, since z = s −x −y. (ii) 10 \leqs \leq17. In this case the second move is (9, s −9, 0). The answer is z + (9 −x) + |x + z −9| = 2k, where k = z if x + z \geq9, or k = 9 −x if x + z < 9. In both cases we have z \leqk \leqy + z \leqs. Let s −k \leq9. Then in the third move we ask (s −k, 0, k) and obtain |z−k|+|k−y−z|+y, which is actually (k−z)+(y+z−k)+y = 2y. Thus we also find out x + z, and thus deduce whether k is z or 9 −x. Consequently we determine both x and z. Let s −k > 9. In this case, the third move is (9, s −k −9, k). The answer is |s −k −x −y| + |s −9 −y −z| + |k + 9 −z −x| = (k −z)+ (9−x)+ (9−x+k −z) = 18 +2k −2(x+z), from which we find out again whether k is z or 9 −x. Now we are easily done.

(iii) 18 \leqs \leq27. Then as in the first case, asking (0, 9, 9) and (9, 0, 9) we obtain x and y.