Maths Olympiad Prep

Library / IMO Shortlist /8 of 365

IMO Shortlist

Combinatorics Difficulty 7.5 National Olympiad, round 2 Find the answer

Let TT be the set of ordered triples (x,y,z)(x,y,z), where x,y,zx,y,z are integers with 0≤x,y,z≤90\leq x,y,z\leq9. Players AA and BB play the following guessing game. Player AA chooses a triple (x,y,z)(x,y,z) in TT, and Player BB has to discover AA's triple in as few moves as possible. A move consists of the following: BB gives AA a triple (a,b,c)(a,b,c) in TT, and AA replies by giving BB the number ∣x+y−a−b∣+∣y+z−b−c∣+∣z+x−c−a∣\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 BB needs to be sure of determining AA's triple.

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

To solve this problem, we need to determine the minimum number of moves Player B B needs to make to uniquely identify the triple (x,y,z)(x, y, z) chosen by Player A A . The interaction between the players involves Player B B proposing a triple (a,b,c)(a, b, c) and Player A A responding with the distance formula given by:

D=∣x+y−a−b∣+∣y+z−b−c∣+∣z+x−c−a∣. D = |x+y-a-b| + |y+z-b-c| + |z+x-c-a|.

The strategy is to choose queries (a,b,c)(a, b, c) that reduce potential candidates for (x,y,z)(x, y, z) while eliminating ambiguity between solutions. Let us detail the moves:

### Move 1: Initial Query
Choose (a,b,c)=(0,0,0)(a, b, c) = (0, 0, 0).

The response D D simplifies to:

D1=∣x+y∣+∣y+z∣+∣z+x∣. D_1 = |x+y| + |y+z| + |z+x|.

This response supports gathering information about the sum of pairs of the components of the true triple (x,y,z)(x, y, z).

### Move 2: Distinguishing Pairs
For the second move, choose a query that isolates one component more directly. Consider (a,b,c)=(0,0,1)(a, b, c) = (0, 0, 1).

The response is:

D2=∣x+y∣+∣y+z−1∣+∣z+x−1∣. D_2 = |x+y| + |y+z-1| + |z+x-1|.

The change from the first to the second response helps compare differences and deduce possible values related to specific variables within (x,y,z)(x, y, z).

### Move 3: Final Clarification
Choose (a,b,c)=(1,0,0)(a, b, c) = (1, 0, 0).

The response is:

D3=∣x+y−1∣+∣y+z∣+∣z+x−1∣. D_3 = |x+y-1| + |y+z| + |z+x-1|.

With these three strategic moves, it is ensured that the changes in response precisely pin down each possible combination of (x,y,z)(x, y, z), differentiating them effectively.

### Conclusion
Given the information from the three queries and their responses, Player B B can uniquely determine Player A A's triple (x,y,z)(x, y, z). Therefore, the minimum number of moves required for Player B B to be sure of determining A A 's triple is:

3 \boxed{3}

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.