2002 IMO Shortlist Problems/C4
(Bulgaria) Let be the set of ordered triples , where , , are integers with . Players and play the following game. Player chooses a triple in , and Player has to discover 's triple in as few moves as possible. A move consists of the following: gives a triple in , and replies by giving the number . find the minimum number of moves that needs to be sure of determining 's triple.
In mod 2, we see that
so the outcome of '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 possible triples and at most possible outcomes after two moves, at least three moves are required.
We will now show how to determine in three moves. A first move of will give us . We shall denote as .
If , then the moves and will give us and , respectively, enabling us to determine . Similarly, if , the moves and will give us and .
If , then our second move is . Let us call the result . We have two cases. In Case I, , which gives us , . In Case II, , so and . In either case, we have (the right-hand side comes from or ) and .
Now, if , then our third move is . This gives us
which gives us and tells us whether Case I or Case II holds, letting us determine .
On the other hand, if , our third move is . This gives us
which again gives us , telling us which of Cases I and II hold, letting us determine the triple .
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.