Maths Olympiad Prep

Library / /13 of 144

Combinatorics Difficulty 7.6 National olympiad, round 2 Find the answer

AA and BB play a game, given an integer NN, AA writes down 11 first, then every player sees the last number written and if it is nn then in his turn he writes n+1n+1 or 2n2n, but his number cannot be bigger than NN. The player who writes NN wins. For which values of NN does BB win?

[i]

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

Solution

To determine for which values of N N player B B wins, we need to analyze the structure of the game and identify a strategy that ensures victory for player B B .

### Game Analysis

Given the rules of the game:
- Player A A starts by writing the number 1 1 .
- Each player alternates turns writing either n+1 n+1 or 2n 2n , where n n is the last number written.
- The number written cannot exceed N N .
- The player who writes N N wins.

To solve the problem, we must deduce for which values of N N , player B B is guaranteed a win regardless of how optimally player A \ plays. ### Winning and Losing Positions In combinatorial game theory, we identify "winning" and "losing" positions: - **Winning Position:** A position where the player whose turn it is can force a win with optimal play. - **Losing Position:** A position where the player whose turn it is will lose with optimal play from the opponent. The strategy involves determining the losing positions. Player \( B will win if and only if A A begins his turn in a losing position.

### Characterizing Losing Positions

1. Base Case:
- N=1 N = 1 is a losing position because player A A starts and immediately wins.

2. Recursive Analysis:
- If writing n n is a losing position, then both n+1 n+1 and 2n 2n must be winning positions.
- Conversely, n n is a winning position if either n+1 n+1 or 2n 2n is a losing position.

By iteratively applying these conditions, we can deduce:
- A position n n is losing if n n is the sum of distinct odd powers of 2. These are numbers whose binary representation consists of zeros and a single one in an odd position.

### Examples and Verification

For example, consider N=3 N = 3 .
- N=1 N = 1 is losing (as defined above).
- Starting from 1, player A A can choose 2.
- Then, player B B can choose 3 and win. Hence, 3 was a winning position for B B .

Values of N N being sums of distinct odd powers of 2 include N=1,3,5,9,17, N = 1, 3, 5, 9, 17, \ldots . In binary, these are 1, 11, 101, 1001, 10001, corresponding to 20,21+20,22+20,23+20,24+20, 2^0, 2^1 + 2^0, 2^2 + 2^0, 2^3 + 2^0, 2^4 + 2^0, \ldots .

### Final Conclusion

Player B B wins for values of N N that are sums of distinct odd powers of 2. Therefore, the answer is:

N=the sum of distinct odd powers of 2 \boxed{N = \text{the sum of distinct odd powers of } 2}

This strategy ensures that player B B will always find themselves in a winning position when N N fits this pattern. The correct identification of such N N solidifies player B B 's chances of winning.

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.