Formula for NimDate: 02/22/2002 at 15:20:56 From: Kentaro Miura Subject: NIM Hi. I have been attempting to figure out a formula for the game called the Chip Game. You can play with any number of chips. Each player takes turns to eliminate up to three coins at a time. The person to take the last chip loses the game. (For example, there are 5 chips. The first person takes 1 chip. His opponent takes 3 chips. The person that took the first one lost.) I have gained the ability to win some games. However, I would like to know a complete formula that applies for any number. Thank you. Date: 02/22/2002 at 23:23:03 From: Doctor Twe Subject: Re: NIM Hi Kentaro - thanks for writing to Dr. Math. This is one version of a popular mathematical game commonly called NIM. If you type "nim" (without the quotation marks) and select "complete words only" in our Ask Dr. Math archive searcher at: http://mathforum.org/mathgrepform.html You'll find a half dozen answers relating to the game of NIM and its variants. Let's start with a simple game. Assume we play first, and that our opponent will play his best possible move each time. Suppose we start with 4, 3, or 2 coins. What is our strategy? Simple; take all but 1 coin. Our opponent has to take the last coin and lose. Now suppose that we start with 5 coins. * If we take 1 coin (leaving 4), our opponent will take 3 - we lose. * If we take 2 coins (leaving 3), our opponent will take 2 - we lose. * If we take 3 coins (leaving 2), our opponent will take 1 - we lose. No matter what we do at 5 coins, we lose. Next, suppose we start with 6 coins. * If we take 1 coin, we leave our opponent with 5 - which we showed was a losing position for him. * If we take 2 coins (leaving 4), our opponent will take 3 - we lose. * If we take 3 coins (leaving 3), our opponent will take 2 - we lose. So our winning strategy is to take 1 coin, leaving our opponent with the losing position of 5 coins. Suppose we start with 7 coins. * If we take 1 coin (leaving 6), our opponent will take 1 - leaving us with 5 - we lose. * If we take 2 coins, we leave our opponent with 5 - a losing position. * If we take 3 coins (leaving 4), our opponent will take 3 - we lose. So our winning strategy is to take 2 coins, leaving our opponent with the losing position of 5 coins. Likewise if we start with 8 coins. * If we take 1 coin (leaving 7), our opponent will take 2 - leaving us with 5 - we lose. * If we take 2 coins (leaving 6), our opponent will take 1 - leaving us with 5 - we lose. * If we take 3 coins, we leave our opponent with 5 - a losing position. So our winning strategy is to take 3 coins, leaving our opponent with the losing position of 5 coins. Now, suppose we start with 9 coins. * If we take 1 coin (leaving 8), our opponent will take 3 - we lose. * If we take 2 coins (leaving 7), our opponent will take 2 - we lose. * If we take 3 coins (leaving 6), our opponent will take 1 - we lose. No matter what we do at 9 coins, we lose. Suppose we start with 10 coins. * If we take 1 coin, we leave our opponent with 9 - which we showed was a losing position. * If we take 2 coins (leaving 8), our opponent will take 3 - we lose. * If we take 3 coins (leaving 7), our opponent will take 2 - we lose. So our winning strategy is to take 1 coin, leaving our opponent with the losing position of 9 coins. We can continue this, but let's put it in chart form: # Coins We take Leaving ------- ------- ------- 1 1 0 We lose. 2 1 1 Opponent must take it and lose. 3 2 1 4 3 1 5 X X Whatever we take, we lose. 6 1 5 Opponent will lose. 7 2 5 8 3 5 9 X X Whatever we take, we lose. 10 1 9 Opponent will lose. 11 2 9 : : : Do you see the pattern? Every fourth number -- 1, 5, 9, 13, ... - is a losing number. We want to leave our *opponent* with that many coins at the start of his turn. To do that, we must get to the nearest losing number, and then match his every move. If he takes N coins, we take 4-N to get to the next losing number. For example, suppose we start with 20 coins. The nearest losing number is 17, so we take 3. Suppose our opponent takes 2, leaving 15. We then take 4-2 = 2 to get to the next losing number, which is 13. Suppose he next takes 3, leaving 10. We then take 4-3 = 1 to get to the next losing number, which is 9. Suppose he next takes 1, leaving 8. We then take 4-1 = 3 to get to the next losing number, which is 5. At this point, he realizes that he can't win, but takes 1 as a formality, leaving us 4. We take 3, and he must take the last one - we win! Try a few games, and then see if you can find the winning strategy for the following variants: * Each player may take between 1 and 4 coins. (Or between 1 and N coins.) * The player who takes the last coin wins. * There are 2 (or more) piles of coins. Each player may only take coins from one pile. I hope this helps. If you have any more questions or comments, write back again. - Doctor TWE, The Math Forum http://mathforum.com/dr.math/ Date: 02/27/2002 at 16:07:59 From: Doctor Anthony Subject: Re: NIM The general approach to the game of NIM is described below. The technique is to express the number of coins in each pile in binary scale and add the coefficients of the various powers of 2. You then remove as many coins from some pile or other as necessary to leave the sum of the coefficients of each power of 2 an even number. When the opponent draws he is bound to upset such an arrangement and you then repeat the process. The only exception is that you must not leave an even number of piles containing one coin each. We can lay out the problem as follows, with three piles containing say 3, 4, and 5 coins respectively Pile(1) Pile(2) Pile(3) 11 (pile(1) in binary) ------- ------- --------- 100 (pile(2) in binary) *** **** ***** 101 (pile(3) in binary) ----- 212 = Sum of columns We want the sum of each column to be even (or zero) and we can do this by making pile(1) = 1 instead of 11. So we reduce pile(1) to 1. This means we must take 2 coins from pile(1). We then get: 1 100 101 ----- 202 This is now a winning position. When the opponent takes any coins he is bound to leave some column odd, and you can repeat the above calculation to get back to each column having an even total. As mentioned before, you must not leave an even number of piles with one coin in each (this does give an even sum to the column 2^0), and in this case you must leave an ODD number of piles with one coin in each pile. - Doctor Anthony, The Math Forum http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/