Maths Olympiad Prep

Library / /87 of 105

Combinatorics Difficulty 6.6 National Olympiad Prove it JBMO

Problem:

Alice and Bob play the following game: starting with the number 22 written on a blackboard, each player in turn changes the current number nn to a number n+pn + p, where pp is a prime divisor of nn. Alice goes first and the players alternate in turn. The game is lost by the one who is forced to write a number greater than 222020\underbrace{2 \ldots 2}_{2020}. Assuming perfect play, who will win the game.

Solution

Solution:

We prove that Alice wins the game. For argument's sake, suppose that Bob can win by proper play regardless of what Alice does on each of her moves. Note that Alice can force the line 246810122 \rightarrow \mathbf{4} \rightarrow 6 \rightarrow \mathbf{8} \rightarrow 10 \rightarrow \mathbf{12} at the beginning stages of the game. (As each intermediate 'position' from which Bob has to play is a prime power.) Thus the player on turn when the number 1212 is written on the blackboard must be in a 'winning position', i.e., can win the game with skillful play. However, Alice can place herself in that position through the following line that is once again forced for Bob: 2469122 \rightarrow \mathbf{4} \rightarrow 6 \rightarrow \mathbf{9} \rightarrow 12. (This time she is in turn with 1212 written on the blackboard.) The obtained contradiction proves our point.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.