(NOTE: Check out the other posts in The Secrets of Nim series.)
Since I talked so much about Nim in my previous post, I thought it might be interesting to take a deeper look at the game. There are many places that discuss how to win at Nim, but not too many that discuss WHY these plays are the winning plays.
Terminology
There are actually several versions of Nim, so it's best to get our terms straight first.
Nim is a two-player strategy game in which players take turns removing objects from distinct heaps.
In what I'll call standard Nim, or simply Nim, the winner is the person who takes the last object. In what is known as Misère (pronounced "Meez-air") Nim, the loser is the person who takes the last object.
There are also single-pile versions of Nim, in which you can only remove a limited number of objects in each turn, and multi-pile nim, where you can remove as many objects in each move as you wish, but only from a single pile. In this post, we'll be focusing exclusively on single-pile Nim, and save multi-pile Nim for my next post.
Winning Strategy And The WHY
The most oft-encountered version of single-pile Nim is Misère Nim, where each player may take either one, two, or three objects in each turn, and the player who takes the last object is the loser.
This video below gets right to the point as to WHY the winning approach works:
It's easy to see why the “group of 4” strategy works with 5 objects, and note that it works with 9, 13, 17 or any other number that's 1 greater than a multiple of 4. The technical term for this is modular arithmetic, given a clear explanation here by BetterExplained.
Modular arithmetic is something you've been doing for most of your life, but without the fancy terminology. If two people are talking on the phone at 10 AM, and agree to meet at their favorite restaurant for dinner in 8 hours, when are they going to meet? That's right, they're meeting at 6 PM.
This post was put up on July 29th. My next post will be done on Sunday, 3 days from now. My next post after that will be next Thursday, 1 week from now. What are the dates of my next two posts? August 1st and August 5th.
Both of those examples required modular arithmetic to answer. In the first case, you mentally figure 10 + 8 to get 18. Because you're so used to a 12-hour clock, it was easy to work out that 18 - 12 = 6, thus the answer must be 6 PM. What you're basically saying here is that, ignoring 12s, 10 + 8 is the same as 6.
Similarly with the months of the year, ignoring 31s (the number of days in July), the 1st is the same as the 32nd (29 + 3 = 32), and the 5th is the same as the 36th (29 + 7 = 36).
So how does this help in Misère Nim? First, the limit to the number of objects that either player can remove at one time is limited to less than 4 (1, 2, or 3 objects), so that the 2nd player can take advantage of the 1st player's move to get to total 4 objects.
Since, as we've already determined, that if we ignore 4s (referred to in mathematics as “modulo 4”), that leaving 17 objects (or 13, or 9, etc.) is the same as leaving 1 object, you can see why the game is won so far ahead of time.
Notice that, if you go first, or make a mistaken move, it is still possible to win by looking for opportunities to get the pile to 1 over any multiple of 4.
Let's say you have 17 objects, and the other player removes 2 (leaving 15). You should take 2, but let's say you take 3 by mistake (leaving 12). Now your opponent takes 1 (leaving 11) what do you do? You need to get to the next number that's 1 above a multiple of 4. 9 is that number, and you can get there by removing 2 objects!
Note that there's nothing special about using the number 4. We could use a number of objects that's one greater than a multiple of 5 (“modulo 5”), say 26 (25 + 1), and allow the each player to remove 1, 2, 3, or 4 objects (4 being 1 less than 5) in each round.
To take this to a silly extreme, we could have a pile of 501 objects (1 plus a multiple of 100), and allow anywhere from 1 to 99 (1 less than 100) objects to be taken each time. It might be hard to know how many your opponent takes in this case, but if you could determine that in some manner, just take enough to total 100 (Opponent took 47? You take 53! That's “modulo 100”). Now you see why the “modulo 4” caught on so much quicker than this version.
Notice that, in order for you to win, you must use information provided by your opponent's move, and therefore they must go first. What if your opponent gets suspicious of your constant winning, and wants you to go first? The age-old answer, as shown in Scam School's 8th episode, is to cheat by ringing in an extra match, and making your opponent believe that you're removing this extra match from the pile. The pile still has the same number of matches, and you can proceed as normal from here.
The alternative is get lucky and recover as described above.
Variations
Once you understand the basics behind single-pile Misère Nim, you can also develop alternative versions. If your opponent either doesn't understand Nim, or knows the winning strategy for one particular version without understand the reasons behind it, this can help you get a new advantage.
What about turning Misère Nim into standard Nim, where the person who removes the last object(s) is/are the winner? This is easy – start with 1 less object! Instead of playing with 17 or 13 objects, start with 16 or 12. Using the same modular arithmetic as above, ignoring 4s, leaving them with 16, 12, 8, or 4, is the same as leaving them with 0!
We keep focusing on objects, but you don't even need objects! Misère Nim can also be played verbally. One of the more popular verbal versions is “21”. The first player starts stating either the numbers 1, 2, or 3 out loud. The other player then adds 1, 2, or 3 to that number and gives the new total. The first player then adds 1, 2, or 3 more to the running total, and gives that number. The person forced to say “21” loses (you're not allowed to give a total over 21).
Since the only difference here is cosmetic, this game is played exactly as if it were being played with 21 objects! If the other person goes first, you can always win just as in the original game. If you go first, you can really only recover by taking advantage of mistakes made by your opponent, as described earlier in this post.
You can mix these variations together, too. What about a Nim game where the winner is the first person to get to 100? Here's how that breaks down:
1) OK, the game is verbal, so we use no objects. As discussed before, this is only a cosmetic change, and doesn't affect play or strategy.
2) We'll take advantage of the fact that 100 is 1 greater than 99. 99 is a multiple of 3, 9, and 11. Using 3 would mean limiting the numbers added to 1 or 2 at a time. 9 wouldn't be bad, as the choice of numbers 1-8 would move the game along quickly, but 1-8 is an unusual range. How about 11 “modulo 11”? You could add numbers from 1-10 (a normal sounding range), and the game would move quickly, but be long enough to appear challenging!
3) Using 11 not only means that the choices are from 1-10, but also that our key numbers will be 1, 12, 23, 34, 45, 56, 67, 78, 89, and 100 (each 1 greater than a multiple of 11). These are pretty easy to remember, since each number except 100 has a sequential appearance (1 is after 2, so 12 is easy to remember, and so on).
4) You could also create a version where you played down to zero. However, changing direction does change the key positions you need to achieve. Starting from 100, only allowing the numbers 1-10, and playing down to 0 (where the person taking the last object wins), means your key positions are 99, 88, 77, 66, 55, 44, 33, 22, and 11. As learned with the version taught in the first video above, when counting down, your key positions are always multiples of your modulo number.
In their 116th episode, Scam School taught this version, along with a calendar version of Nim which I submitted:
Notice that, in the calendar version, you're working with two factors – a month and a date. In this case, to win you need to keep their relationship to a certain constant. Since your target date is 12/31, and 31-12 has a difference of 19, all the dates you get to must also have that difference of 19. Yes, the calendar race is a well-disguised modulo 19 version of Nim!
As noted in my post on that episode, going from 12/31 to 1/1 is even easier, as your target dates become 12/12, 11/11, and so on, down to 1/1! Believe it or not, this make the January 1st version a “modulo 0” Nim game.
I'll wrap up this part of my Nim series with 2 final interesting variations. The first is the card version, called “31”:
This card version which has several interesting layers to it. It's easy to understand that this is a “modulo 7” game, so that the numbers used in each turn are limited from 1 through 6. But why isn't the game played to 29 (as opposed to 31), which is 1 greater than a multiple of 7?
This is the final dirty secret of single-pile Nim. Your key states don't have to be limited to a number 1 greater than the “modulo” number you're using. As you as you play to move to numbers that are equivalent in modular arithmetic to that of your goal, you can use any amount.
In 31, ignoring 7s, the numbers 3, 10, 17, and 24, are all the same as 31. They're all 3 above a multiple of 7.
Let's say you're a Douglas Adams fan, and want to create a verbal version where the winner is the person who reaches 42. It's 1 above 41, which is prime, so it's only a multiple of 1 and 41. So how about using 40? We could set it up using 4 or 5 as our modulo number, but I like 8. So, each person can add 1 to 7 each time. Your goal number all have to be 2 greater than multiples of 8 in this case, just like 42. Therefore, the key numbers you play to are 2, 10, 18, 26, and 34 (and 42, of course).
Another layer of the card/31 version is the use of a limited number of cards. Winning number 31 is 3 over 28, which is a multiple of 7, which is knowledge you use to win the first game. However, 28 is also a multiple of 4 (the number of cards in each pile), which helps in winning the 2nd game where you win while you're teaching.
When you teach the key numbers (3, 10, 17, 24, and 31) the first time, they naturally pick up the 3 first. You take the 4 to get to 7, so they have to take the 3 to get to the next key number (10). Taking all four 3s and all four 7s comes to 28. Now, it's no longer possible to choose 3 or 4. 5 and 6 would take you past 31, so the only real choices left are aces (1s) and 2s. If they take 1, you take the other, and you still win!
This is why the number 31 was so specifically chosen for this version of the game. It works in the first game, which is really “modulo 7”. When teaching the game, the game is effectively changed to “modulo 4”, which works until all the 3s and 4s are gone, at which point the game suddenly changes to “modulo 3” without warning! This is very sneaky.
Pop Quiz: What if you wanted to start from 31, and play down to 0, allowing only from 1 to 6 objects to be removed? What would your key positions be then? It's a modulo 7 game, so you would simply play down to the multiples of 7: 28, 21, 14, and 7.
The Importance of Understanding Nim
Our final video in this part of our Nim series shows why it's not just important to know the winning moves of Nim, but the why behind it. In this video, 2 men learn the simpler secret to winning Nim, but their failure to understand the reasoning behind it costs them financially:
In part 2 on Sunday, we'll begin our look into the secrets behind multi-pile Nim.
Posts
3 Response to The Secrets of Nim (Part 1)
Great! Very clear and nice links.
Very nice post! Thank you very much!
Really useful information here, succinct and clear. We've linked to you from our most recent post on our maths education blog - http://mathsticks.com/my/2016/01/celebration-maths-challenge/
Post a Comment