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?
3 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 2 = 784 = 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 = 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  Z. So we certainly have Z  9. 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 (C) John Scholes jscholes@kalva.demon.co.uk 14 Aug 2003 Last corrected/updated 14 Aug 2003