Consider a two player game. There are N balls marked 1 to N. A move consists of removing a ball n and all other balls which are divisors of n (including 1). The players alternate the moves. The one who takes the last ball wins the game.
Eg. [1 ,2 ,3 , 4, 5][Player 1 (4, 2, 1)]>[3, 5][Player 2 (3)]>[5][Player 1 (5)]>[]. Player 1 wins. The () contains the balls a player removes.
I tried solving the problem for N < 10 manually and was able to observe that it was always possible to force victory for player who starts the game. I also know that this is always the case for all N from here. Can someone share the proof of this result and the playing strategy?
I tried to use the strategy stealing argument from the game of chomp but I am not sure if it is applicable here.
Take the 2minute tour
×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.



One can indeed prove that the first player has a winning strategy using the classical strategy stealing argument. If the second player had a winning strategy, the first player would just play "1" and then follow the second player's winning strategy. This works since any move by the second player would also remove the number "1", thus the the state of the game after the second player's turn would be a valid state of the game after a single move. 

