Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question

1 Answer 1

up vote 3 down vote accepted

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.

share|improve this answer
    
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 Nim`s game or it`s proven that it can`t be found? –  forcebrute Apr 7 '12 at 6:12
    
I did not think about this particular game, but in chomp it is a notable open problem. –  Ori Gurel-Gurevich Apr 7 '12 at 17:48

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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