Maths Olympiad Prep

Library / /4 of 4

Combinatorics Difficulty 6.3 National olympiad Prove it Austria

On the occasion of the 47th Mathematical Olympiad 2016 the numbers 4747 and 20162016 are written on the blackboard. Alice and Bob play the following game. Alice begins and in turns they choose two numbers aa and bb with a>ba > b written on the blackboard, whose difference aba - b is not yet written on the blackboard and write this difference additionally on the board. The game ends when no further move is possible. The winner is the player who made the last move.
Prove that Bob wins, no matter how they play.

Solution

We consider the set BB of the numbers on the blackboard at the end of the game. It is clear that B{1,,2016}B \subseteq \{1, \dots, 2016\}. Let m=minBm = \min B and nBn \in B. We claim that mnm \mid n. Otherwise, write n=qm+rn = qm + r with 0<r<m0 < r < m. By induction on kk, we have nkmBn - k m \in B for 0kq0 \le k \le q (because no more moves are possible, these numbers must be on the blackboard). Thus r=nqmBr = n - q m \in B, which contradicts the minimality of mm.

We conclude that m1=gcd(2016,47)Bm \mid 1 = \gcd(2016, 47) \in B. By induction on cc, we have ncBn - c \in B for 0c20150 \le c \le 2015. This also implies that B={1,,2016}B = \{1, \dots, 2016\}.

As 22 numbers had been on the blackboard at the beginning of the game, the game ends after 20142014 moves when all other numbers have been written. Therefore, Bob wins after move 20142014.

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: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.