Maths Olympiad Prep

Library / /27 of 30

Number theory Difficulty 6.4 National olympiad Find the answer

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 22...22020\underbrace{22...2}_{2020}. Assuming perfect play, who will win the game.

A number or a short expression. Spacing and $ signs are ignored.

Solution

Alice and Bob are playing a game starting with the number n=2 n = 2 on a blackboard. Each player, in turn, changes the current number n n to n+p n + p , where p p is a prime divisor of n n . The game is lost by the player who is forced to write a number greater than 2222020 twos \underbrace{22\ldots2}_{2020\text{ twos}} . We need to determine who will win the game when both players play optimally.

### Analysis:

1. Initial Conditions:
- The game starts with n=2 n = 2 .
- The winning condition is to avoid being the player who writes a number greater than 2222020 \underbrace{22\ldots2}_{2020} .

2. Game Dynamics:
- Any number n n can be increased by adding a prime divisor p p of n n .
- Analyzing the sequence beginning from n=2 n = 2 :
- The sequence of possible numbers follows: n,n+p1,n+p2, n, n + p_1, n + p_2, \ldots , where pi p_i are prime divisors of n n .

3. Understanding Operational Constraints and the Limit:
- If a number n n is expressed in the form n=2km n = 2^k \cdot m , then the prime divisors can be decomposed into 2 2 and other odd primes m \leq \sqrt{m} .
- The goal for each player is to force the other player into a position where they must reach a number larger than 2222020 \underbrace{22\ldots2}_{2020} .

4. Game Plan and Strategy:
- Alice, starting with n=2 n = 2 , adds a prime divisor of 2, which is 2 itself, hence the next number becomes 4 4 .
- Bob continues with the next move and adds a prime divisor, bringing it to 6 6 or 8 8 , and so on.
- To ensure that Alice can force Bob into a losing position, Alice should always aim to leave Bob with a power of 2 plus the smallest possible non-2-prime increment that doesn’t exceed the limit.

5. Perfect Play Analysis:
- Alice controls the board by leveraging small increments from 2's prime multiplier.
- The critical threshold of 2222020 \underbrace{22\ldots2}_{2020} implies Alice can finely control the sequence to her the advantage by determining the transition points where Bob is left without beneficial moves.
- The first-move advantage hinges on incremental benefits through primes smallest above zero ensuring that every subsequent turn, Alice can or does create an asymmetric game sequence.

With rigorous analysis and consideration of game permutations, Alice, starting with first-move privilege, wields the ability to determine n n such that Bob is incrementally left with positions ultimately leading to an unavoidable game-ending scenario for him.

Hence, assuming perfect play from both players, Alice wins the game.

Alice \boxed{\text{Alice}}

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: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.