Alex and Bella play the following game. They first choose a positive integer N, and take turns writing numbers on a blackboard. Alex starts first, and writes the number 1. After that, if the number k is on the board, the next player may write down either k+1 or 2k, if the new number is not greater than N, and then erase k. The player who writes Non the blackboard wins. For how many integers N≤1000 does Bella have a winning strategy?
Details and assumptions
Both players will play to win for themselves
998
To determine how many integers N ≤ 1000 Bella has a winning strategy for, we need to analyze the game and figure out the conditions under which Bella can guarantee a win.
Let's first understand the game's rules. Alex and Bella take turns writing numbers on a blackboard, starting with Alex writing the number 1. If a player writes the number k on the blackboard, the next player can choose to write either k+1 or 2k, but only if the resulting number is not greater than N. The player who writes Non the blackboard wins.
Now let's break down the game and identify the winning strategy for Bella. We'll analyze it step by step:
1. For small values of N (N ≤ 3):
- When N = 1, Alex can write 1, and he wins since Bella has no valid moves.
- When N = 2, Bella chooses to write 2, and she wins since Alex has no valid moves.
- When N = 3, Bella chooses to write 2, leaving Alex with the number 3. Bella can now mirror Alex's moves, always choosing the opposite option (for example, if Alex writes k+1, Bella writes 2k, and vice versa). This way, Bella will always be able to write N on the blackboard, winning the game.
In total, Bella has a winning strategy for 3 different integers in this range.
2. For larger values of N (N > 3):
- If N is an even number, Bella can always mirror Alex's moves after he writes the number 2. This way, Bella ensures that she can always write N on the blackboard, winning the game. For example, if N = 4, Bella responds to Alex's 2 with a 3, and then mirrors the rest of his moves.
- If N is an odd number, Bella's strategy will depend on the highest power of 2 that is less than or equal to N. Let's call this power of 2 "M." Bella chooses to write N-M.
- If N - M = 1, Bella knows that Alex will write N on his turn, so Bella has a winning strategy.
- If N - M > 1, Bella mirrors Alex's moves after he writes N - M - 1, effectively guaranteeing that she can write N on the blackboard, winning the game.
For example, if N = 7, the highest power of 2 less than or equal to 7 is 4. Bella chooses to write 3. If Alex writes 4, Bella writes 7 next. If Alex writes 5, Bella writes 6. No matter what choices Alex makes, Bella can always write N on the blackboard, winning the game.
By following these strategies, Bella can guarantee a win in every game where the value of N falls under the conditions we outlined. To find the count of such integers N ≤ 1000, we can iterate through the range [1, 1000] and apply the above analysis to each value of N.
I hope this explanation helps you understand the winning strategy for Bella and how to find the count of integers N ≤ 1000 where she has a winning strategy.