7
$\begingroup$

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.

  • 1
    This is still an impartial game. If you follow the proof in http://www.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.2011-04-18

1 Answers 1

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.

  • 0
    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)?2011-04-18