Olympiad Maths Prep

Library /

Combinatorics Difficulty 4.8 AIME Prove it Austria

The nonnegative integers 20002000, 1717 and nn are written on a blackboard. Alice and Bob play the following game: Alice begins, then they play in turns. A move consists in replacing one of the three numbers by the absolute difference of the other two. No moves are allowed where all three numbers remain unchanged. A player in turn who cannot make a legal move loses the game.
* Prove that the game will end for every number nn.
* Who wins the game in the case n=2017n = 2017?

Solution

If three numbers are written on the blackboard and one of them is replaced by the (positive) difference of the other two, then after this move one number on the blackboard will be the sum of the other two. Let aa, bb and a+ba+b be the numbers on the blackboard; w.l.o.g. we assume that b>ab > a. Because of a+bb=aa+b-b=a and a+ba=ba+b-a=b there is only one possible move. After it the numbers aa, bb and bab-a are written on the blackboard. Again, one number (namely bb) is the sum of the other two and there exists only one possible move.
This means that at the latest from the second turn on there is no choice of moves and all moves are inevitable. Furthermore, from the second move on, the largest of the three numbers is decreased, and since no number can become negative, after a finite number of moves one of the numbers will be 00. Since 00 is the difference of the other two numbers, we must have 00, aa, aa on the blackboard. Now a0=aa-0=a and aa=0a-a=0, therefore no further move is possible. Thus the player writing 00, aa, aa onto the blackboard is the winner.
If the game starts with the numbers 20002000, 1717 and 20172017 on the blackboard, the course of the game is as follows:
1st move (A): 20002000, 1717, 19831983
2nd move (B): 19661966, 1717, 19831983
3rd move (A): 19661966, 1717, 19491949
etc. (since 2000:17=117.62000 : 17 = 117.6 ...)
117th move (A): 200011617=282000 - 116 \cdot 17 = 28, 1717, 200011717=112000 - 117 \cdot 17 = 11
118th move (B): 66, 1717, 1111
119th move (A): 66, 55, 1111
120th move (B): 66, 55, 11
121st move (A): 44, 55, 11
122nd move (B): 44, 33, 11
123rd move (A): 22, 33, 11
124th move (B): 22, 11, 11
125th move (A): 00, 11, 11
and A wins the game.

Looking for a route rather than an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.