For positive integers a -[i]game[/i] is a two player game defined by the following rules. Initially, the number is written on a blackboard. At his first move, the 1st player replaces with either or . Then, the 2nd player subtracts either or from this number, and writes the result on the blackboard, erasing the old number. After this, the first player once again erases either or from the number written on the blackboard, and so on. The player who first reaches a negative number loses the game. Prove that there exist infinitely many values of for which the first player has a winning strategy for all pairs with .
Problem 1506
Official solution
1. Initial Setup and Definitions:
- We are given a game with initial number and two positive integers and such that .
- Players take turns subtracting either or from the current number on the blackboard.
- The player who first reaches a negative number loses the game.
2. Inductive Hypothesis:
- Suppose Player 1 has a winning strategy for some initial number where .
- We need to show that Player 1 also has a winning strategy for for any positive integer .
3. Base Case:
- Assume Player 1 wins for where . Let be the sequence of moves that ensures Player 1's win starting from .
4. Inductive Step:
- Consider the game starting with .
- Player 1's strategy is to mimic the sequence but adjusted for the larger initial number.
- Specifically, Player 1 starts by subtracting either or to reduce the number to or .
5. Reduction to Smaller Problem:
- After Player 1's first move, the number on the board is or .
- Player 2 then subtracts either or , resulting in one of the following:
- Notice that , which is .
6. Inductive Argument:
- By the inductive hypothesis, if Player 1 has a winning strategy for , then they also have a winning strategy for .
- Therefore, Player 1 can continue to follow the strategy adjusted for the new starting number .
7. Contradiction and Conclusion:
- Suppose (Player 1 wins starting from ).
- If and , then (Player 2 wins starting from ).
- This implies and , leading to a contradiction since and would imply .
8. Final Proof:
- Therefore, the assumption that leads to a contradiction.
- Hence, must hold, proving that Player 1 has a winning strategy for infinitely many values of .