2002 IMO Shortlist Problems/C4

Problem

(Bulgaria) Let $\displaystyle T$ be the set of ordered triples $\displaystyle (x,y,z)$ , where $\displaystyle x$ , $\displaystyle y$ , $\displaystyle z$ are integers with $0 \le x,y,z \le 9$ . Players $\displaystyle A$ and $\displaystyle B$ play the following game. Player $\displaystyle A$ chooses a triple $\displaystyle (x,y,z)$ in $\displaystyle T$ , and Player $\displaystyle B$ has to discover $\displaystyle A$ 's triple in as few moves as possible. A move consists of the following: $\displaystyle B$ gives $\displaystyle A$ a triple $\displaystyle (a,b,c)$ in $\displaystyle T$ , and $\displaystyle A$ replies by giving $\displaystyle B$ the number $\displaystyle |x+y -a-b| + |y+z -b-c| + |z+x -c-a|$ . find the minimum number of moves that $\displaystyle B$ needs to be sure of determining $\displaystyle A$ 's triple.

Solution

In mod 2, we see that

so the outcome of $\displaystyle B$ 's move must always be even. Furthermore, the outcome must be no greater than 54 and no less than 0, so there are at most 28 different possible outcomes per move. Since there are $\displaystyle 10^3$ possible triples $\displaystyle (x,y,z)$ and at most $\displaystyle 28^2 < 10^3$ possible outcomes after two moves, at least three moves are required.

We will now show how to determine $\displaystyle (x,y,z)$ in three moves. A first move of $\displaystyle (0,0,0)$ will give us $\displaystyle 2(x+y+z)$ . We shall denote $\displaystyle x+y+z$ as $\displaystyle s$ .

If $s \le 9$ , then the moves $\displaystyle (9,0,0)$ and $\displaystyle (0,9,0)$ will give us $\displaystyle 18 -2x$ and $\displaystyle 18 - 2y$ , respectively, enabling us to determine $\displaystyle (x,y,z)$ . Similarly, if $s \ge 18$ , the moves $\displaystyle (0,9,9)$ and $\displaystyle (9,0,9)$ will give us $\displaystyle 2x$ and $\displaystyle 2y$ .

If $\displaystyle 9 < s < 18$ , then our second move is $\displaystyle (9, s-9, 0)$ . Let us call the result $\displaystyle 2k$ . We have two cases. In Case I, $\displaystyle y > s-9$ , which gives us $\displaystyle x = 9-k$ , $\displaystyle z<k$ . In Case II, $y \le s-9$ , so $\displaystyle x \ge 9-k$ and $\displaystyle z=k$ . In either case, we have $\displaystyle z \le k \le y+z$ (the right-hand side comes from $\displaystyle y+z = s-9 +k$ or $z=k , y \ge 0$ ) and $x+z \le 9 + k$ .

Now, if $s-k \le 9$ , then our third move is $\displaystyle (s-k, 0, k)$ . This gives us

$\displaystyle |x+y - s+k| + |y+z -k| + |z+x - s| = k-z + y+z-k + y = 2y$ ,

which gives us $\displaystyle y$ and tells us whether Case I or Case II holds, letting us determine $\displaystyle (x,y,z)$ .

On the other hand, if $\displaystyle s-k > 9$ , our third move is $\displaystyle (9, s-k-9, k)$ . This gives us

$\displaystyle |x+y -s+k| + |y+z -s+9| + |z+x -k-9| = |k-z| + |9-x| + |k+9 -z-x| = 2(k+9-s+y)$ ,

which again gives us $\displaystyle y$ , telling us which of Cases I and II hold, letting us determine the triple $\displaystyle (x,y,z)$ .

Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.

Resources

Page

Toolbox

Search

2002 IMO Shortlist Problems/C4

Problem

Solution

Resources