43rd IMO shortlist 2002/C4 solution

43rd IMO 2002 shortlist

Problem C4

T is the set of all triples (x, y, z) with x, y, z non-negative integers < 10. A chooses a member (X, Y, Z) of T. B seeks to identify it. He is allowed to name a triple (a, b, c) in T. A must then reply with |X + Y - a - b| + |Y + Z - b - c| + |Z + X - c - a|. How many triples does B need to name to be sure of determining A's triple?

Answer

Solution

There are 1000 possible triples. Note that |x| has the same parity as x, so the reply has the same parity as (X + Y - a - b) + (Y + Z - b - c) + (Z + X - c - a) = 2(X + Y + Z) - 2(a + b + c), which is even. Thus the reply must be an even integer in the range 0 through 54, so there are 28 possibilities. Since 28² = 784 < 1000, two replies are not always enough.

Let S = X + Y + Z. B's first triple is always (0, 0, 0). A replies with 2(X + Y + Z) = 2S, so B knows S. If S <= 9, then B asks (9, 0, 0). A replies with (9 - X - Y) + (Y + Z) + (9 - Z - X) = 18 - 2X. Similarly B asks (0, 9, 0) and A replies 18 - 2Y.

Similarly, if S >= 18, then B asks (0, 9, 9). The sum of any two of X, Y, Z must be at least 9 (and is obviously at most 18), so A replies with (X + Y - 9) + (18 - Y - Z) + (Z + X - 9) = 2X. Similarly, B asks (9, 0, 9) and A replies with 2Y.

Suppose 9 < S < 18. Then B asks (9, S - 9, 0). Then A replies (S - X - Y) + (Y + Z - S + 9) + |Z + X - 9| = Z + (9 - X) + |Z + X - 9|. If X + Z >= 9, then this is 2Z, otherwise it is 18 - 2X. Take half the reply to be K. So if X + Z >= 9, then K = Z. If X + Z < 9, then K = 9 - X > Z. So we certainly have Z <= K. Note also that if K = Z, then certainly K <= Y + Z, whilst if K = 9 - X, then K < Y + Z, since S > 9.

If S - K <= 9, then B asks (S - K, 0, K) as his third triple. A replies |X + Y - S + K| + |Y + Z - K| + |Z + X - S| = (K - Z) + (Y + Z - K) + Y = 2Y. So B knows Y. Hence X + Z, so he can decide whether K was Z or 9 - X and gets X or Z. Since he knows S, he as all three.

If S - K > 9, then B asks (9, S - K - 9, K). A replies |X + Y - S + K| + |Y + Z - S + 9| + |Z + X - 9 - K| = (K - Z) + (9 - X) + (K - Z + 9 - X) = 18 + 2K - 2X - 2Z. So B gets X + Z and hence Y. He also can decide if K was Z or 9 - X and so gets X or Z. He knows S, so he gets all three.

43rd IMO shortlist 2002