Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

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

$\displaystyle |x+y -a-b| + |y+z -b-c| + |z+x -c-a| \equiv 2(x+y+z -a-b-c)$,

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

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2002_IMO_Shortlist_Problems/C4&oldid=14392"