Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

We know how to win the classic regular Nim (two players) Classic rules: Any number of beans into any number of separate piles Each move, the player whose turn it is, must choose one pile of beans and remove anywhere from one bean to all the beans in only ONE pile Player taking the last bean looses (as example).

I am looking for the correct strategy for the following variation: Same rules as in the classic regular Nim EXCEPT THAT only once in the game, a player, and only one, MAY PASS his turn.

I found some winning positions 2 1,1 1,N,N (with N>1) 2,3,5 4,5,8, 6,7,3

and I believe that, before the Pass is used, we need to use one "virtual" pile with one bean but I could not find a general strategy.

share|improve this question
2  
What's the difference between the modified game and the original game with one additional one-bean pile? –  Alon Amit Apr 17 '11 at 15:56
    
Do you mean that each player may pass once, or once one player has passed, no other player can pass? –  Thomas Andrews Apr 17 '11 at 16:04
    
I suppose if each player can pass once, then whoever has a winning strategy in the classic game has a winning strategy in the new game, namely: Pass if your opponent passed last time, otherwise play your winning move. On the other hand, @Alon's comment shows how you can translate a "one person can pass once" game into a classic game. –  Thomas Andrews Apr 17 '11 at 16:07
1  
This is still an impartial game. If you follow the proof in amazon.com/Winning-Ways-Your-Mathematical-Plays/dp/1568811306 that every impartial game is a nim-heap, the pass is clearly a one bean heap. –  Ross Millikan Apr 18 '11 at 4:44
add comment

1 Answer 1

In a two-player, zero-sum game with perfect information, a losing position is one from which any legal move leads to a winning position and, a winning position is one from which a losing position may be reached in exactly one legal move, and all positions where no legal moves are possible are losing positions. Nim, viewed in the light of the above recursive definition, involves both players trying to force the other player into a losing position so that irrespective of the move they make, they return you to a winning position.

Update: After Jean-Pierre clarified his question (exactly one PASS move available for both players i.e. after one uses the PASS, then no one else can during the rest of the game)

Conclusion: The first player (P1) is guaranteed a win provided he is not in a winning position from which another winning position cannot be reached.

Strategy: If P1 is in a losing position then he will simply pass, ensuring a win eventually for P1. If P1 is in a winning position, he will play sub-optimally to give to P2 another winning position. If P2 passes now, then P1 can win the game by playing optimally. If P2 chooses to play optimally then P1 can pass and win as in the case when P1 is in a losing position.

If the above assumption fails to hold, i.e., if the winning position P1 is in, is one from which only other winning positions may be reached, then P2 will win by stealing P1's strategy as described above.

share|improve this answer
    
"Zero-sum" is not a relevant adjective for this game. We're really working with Conway/Berlekamp/Guy's partizan games. A pass gives a move to one side, to be sure, but this guarantees a win only when the value of the game for that person was already greater than -1. Because the values of Nim are extremely close to 0, your conclusion is indeed true, but not for the reason you give. –  whuber Apr 17 '11 at 17:44
    
I've divided the set of positions into winning and losing ones and from that the conclusions regarding the variants with a pass move follow. I don't understand why my conclusion is not true for the reason I give. (You can check my previous edit for this question where I explain the strategy, which is the same as the one pointed out by @thomas-andrew above later) –  quantumelixir Apr 17 '11 at 17:54
    
In this problem, only one in the game, a player may pass his turn. There is only ONE pass available for BOTH players .Once one player has passed, no other player can pass. For example, if I give my opponent the position (1,1), if my opponent -uses the PASS, I let him with (1) and I win -plays (1), I use the PASS and I win Other example, if I give my opponent the position (2,2,1), if my opponent: -uses his pass, I let him with (2,2) and I win -plays (2,2), I pass and I win -plays (1,2), I let him with 1 and I win -plays (1,2,1), I give my opponent the position (1,1) and I win –  Jean-Pierre Apr 17 '11 at 22:30
    
Well, in that case too, the first player will always win but for a different reason. See the updated answer; hope this helps answer your question. –  quantumelixir Apr 18 '11 at 4:24
    
Thank you for your comments. Quantumelixir said:"the first player will always win ". Are you sure? For example: How do you play and win if you are the first player and have to play the position (2,2,1)? –  Jean-Pierre Apr 18 '11 at 13:37
add comment

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.