Maths Olympiad Prep

Library / /8 of 144

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 0x,y,z90\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+yab+y+zbc+z+xca\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. Spacing and $ signs are ignored.

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+yab+y+zbc+z+xca. 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+z1+z+x1. 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+y1+y+z+z+x1. 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,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.