Regional Competition

Combinatorics Difficulty 6.3 National Olympiad Prove it Austria

On the occasion of the 47th Mathematical Olympiad 2016 the numbers $47$ and $2016$ are written on the blackboard. Alice and Bob play the following game. Alice begins and in turns they choose two numbers $a$ and $b$ with $a > b$ written on the blackboard, whose difference $a - 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 $B$ of the numbers on the blackboard at the end of the game. It is clear that $B \subseteq \{1, \dots, 2016\}$ . Let $m = \min B$ and $n \in B$ . We claim that $m \mid n$ . Otherwise, write $n = qm + r$ with $0 < r < m$ . By induction on $k$ , we have $n - k m \in B$ for $0 \le k \le q$ (because no more moves are possible, these numbers must be on the blackboard). Thus $r = n - q m \in B$ , which contradicts the minimality of $m$ .

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

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

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.