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.


1 Answer 1


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.

  • $\begingroup$ Well, now I understand that the crux of the strategy stealing is finding a "zero" move which is a subset of any other legal move. Though we can figure out the winning moves with the aid of computer, is it possible to find a general strategy? Is there a mathematical formula as in the case Nims game or its proven that it can`t be found? $\endgroup$
    – Pankaj
    Commented Apr 7, 2012 at 6:12
  • $\begingroup$ I did not think about this particular game, but in chomp it is a notable open problem. $\endgroup$ Commented Apr 7, 2012 at 17:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.