Two players, Abigail and Zoe, play a game. Abigail chooses an odd number less than and writes it on the blackboard. Zoe now chooses a different odd number less than and writes it on the blackboard. Each in turn replaces their number by the difference between their number and the smallest power of bigger than their number. If both players reach on the same move the game is drawn. If not, the player who first reaches loses.
Who has the winning strategy?
Solution
Let be the current number of one of the players. Because both players start with an odd number, will be odd as it remains positive throughout the game. If with is the binary representation of , then . If we assume , then the smallest power of that is bigger than is , hence, the next number for this player will be
where for and . More visually, the effect of one turn is
where and . This new number has at most binary digits, but it may have fewer if was equal to .
In general, all the leading digits will be lost, i.e. if and then the new number will have digits less than . Therefore, the number of turns to reach is equal to the number of blocks of consecutive equal digits in the binary representation of the initial number, where we ignore the last (units) digit in the count.
For example, the smallest number which allows for ten turns is
---
The smallest number that allows for nine turns is .
The number allows for nine turns as well.
Abigail can choose which enables her to carry out nine steps. If Zoe chooses she will also be able to carry out nine steps and so she will win.