The Game of Nim

Hello all-

Before I get to the game of Nim, there are a few things you all will need to know in order to understand my presentation.

Review

1. Binary Numbers

For the CS majors, and probably some of the Math majors, this will be review. If so, feel free to skip. For those who don't know (or don't remember) binary numbers, you can represent any base-10 number (Example: 5, 18, 135) using only zeroes and ones. To do so, you'll need to break the base-10 number down into powers of two.  In binary, the rightmost digit is representative of 2⁰, the second rightmost digit is 2¹, the third rightmost is 2², and so on.

Example:

The number 5 can be written as the sum of 4 + 1, or 2² + 2⁰.This means, that 5 in binary is 101, or 1*2² + 0*2¹ + 1*2⁰.

Example:

The number 18 can be written as the sum of 16 + 2, or 2⁴ + 2¹. Then, in binary, we would represent 18 as 10010.

Example:

Finally, the number 135 can be written as the sum of 128 + 4 + 2 + 1, or 2⁷ + 2² + 2¹ + 2⁰. Hence, in binary, 135 is 10000111.

Got it? Good. If not, Google it.

2. Exclusive-Or

The second thing you'll need to remember is the exclusive or operation. A simple way to remember this is to think of it as arithmetic mod 2. For example, 0 ⊕ 0 = 0, because 0+0 = 0 mod 2. Likewise, 1 ⊕ 1 = 0, because 1+1 = 2 = 0 mod 2. Be careful! One thing to be aware of is 1 ⊕ 1 ⊕ 1 = 1, since 1+1+1 = 3 = 1 mod 2. If this is confusing, don't worry too much. I'll spend some time on this in class.

Also feel free to Google this, or leave a question in the comments- I'll try to answer it in class.

3. N and P Positions

Make sure that you're comfortable with the idea of N and P positions, as we'll use them to analyze Nim. If you're iffy on this, review Natasha's blog post below.

On to Nim!

Ok, so the way Nim works is similar to the subtraction game we played with Natasha in class.

Rules:

1. Start with three piles of objects, call them coins.
2. On your turn, you may remove any number of coins from any pile, but only that pile.
• Example move: Take one coin from one pile, leaving the rest in the pile.
• Example move 2: Take an entire pile, so that there are only two piles left.
3. The game is over when all the coins are gone, or your three piles each have zero coins in them.
4. The person who took the last coin (or pile of coins) wins.

You can play Nim with three piles here by clicking on Level 4. We will also probably play a game as a class during my presentation, just to clear everything up.

The Big Question: When in Nim are you in a P-Position, and when are you in an N-Position?

Before I tell you the answer, feel free to write some conjectures in the comments!

Done? Okay.

It turns out you can calculate whether or not a situation in Nim is a P-Position or N-Position, using binary numbers and exclusive or to calculate the Nim Sum.

Then what's the Nim Sum?

The nim sum is the binary representations of the number of objects in your piles, exclusive-ored together.

Huh?

So, let's say you have three piles in your game, with 13, 12, and 8 objects respectively. Then in binary, you have 1101 (13), 1100 (12), and 1000 (8) objects in each pile. To exclusive-or them, we can line them up vertically, and do our mod 2 arithmetic.

So, our answer is 1001, which in base-10, equals 9. This 9 is our nim sum!

How does that relate to P-Positions and N-Positions?

It turns out, that in any given situation, if your nim sum equals zero, you're in a P-Position. Now let's prove it.

Bouton's Theorem

Bouton's Theorem states that a position in Nim, (x₁, x₂, x₃) is a P-Position if and only if the nim sum of its components is zero, x₁ ⊕ x₂ ⊕ x₃ = 0.

In other words, this is the claim that we need to prove.

Proof

Just like in our Subtraction game proof, let's start our proof by building some sets, and then we'll show that they consist of all the situations that satisfy the definition of P and N Positions.

$$\textit{Let} \ P = \{(x_1, x_2, x_3)| x_1 \oplus x_2 \oplus x_3 = 0\}$$

$$\textit{Let} \ N = \{(x_1, x_2, x_3)| x_1 \oplus x_2 \oplus x_3 > 0\}$$

Also note that there is only one terminal position in Nim, (0,0,0), when the last of the coins has been taken.

Step 1: Show all terminal positions are in P

    This is fairly obvious. We have one terminal position, (0,0,0), and 0 ⊕ 0 ⊕ 0 = 0,
so it's in our set P.

Step 2: For any n ∈ N, you can move to a situation in P.

    Let (n₁, n₂, n₃) be a situation ∈ N. Then n₁ ⊕ n₂ ⊕ n₃ > 0.

    Hence our nim sum is greater than zero.

    So, set up your nim sum columns, and compute your nim sum in binary. Go to the leftmost column in your sum that has a 1. We know that there is one, since our nim sum is greater than zero. Pick one of the piles (n₁, n₂, or n₃) that also has a 1 in that column. Make that 1 a 0, and adjust the rest of the columns of that pile so that you have all 0's in your nim sum.

Note: We will do examples of this in class, because I know it's confusing to read about.

    How do we know we made a legal move? Since the leftmost column is being reduced from a 1 to a 0, we know we're taking objects away from that pile, even if we change the rest of the number to 1's. Hence, you can always take away some number of objects from one pile to move into a P-Position if your nim sum is > 0.

Step 3: For any p ∈ P, you have to move to a situation in N.

    Let (p₁, p₂, p₃) be a situation ∈ P. Then p₁ ⊕ p₂ ⊕ p₃ = 0.

    Then when you set up your nim sum columns, the nim sum is comprised entirely of zeros. Remember: another way to think of exclusive or is arithmetic mod 2. This means that there is no way to change only one pile so that you keep zeros in all the columns. Since you can only change the numbers from zeros to ones and vice versa, changing only one pile will always change one of your nim sum columns from a zero to a one, creating a nim sum > 0.

    Hence, from any position in P, you must move to a position in N.


DONE!

Conclusion

What does all this mean? Basically, it means that for any situation in Nim, it is always possible to figure out whether or not you're in a P-Position or an N-Position. Why is this important? We'll discuss in upcoming classes how Nim is representative of all combinatorial impartial games, but that's beyond the scope of my presentation. Throughout this post, we've discussed and analyzed the game of Nim, using nim sums, and we've talked about how they relate to N and P Positions. We've also proved Bouton's Theorem true, using the same model discussed in class. I'll leave you with some ideas for discussion topics, either in the comments or class:

• Misere Nim: a variation where the last person to take coins loses
• Other variations on Nim
• Does Bouton's Theorem apply to Nim with more than 3 piles?
• Anything you have questions on

Citations:

Bouton, Charles L. "Nim, A Game with a Complete Mathematical Theory." The Annals of Mathematics 3.1/4 (1901): 35-39. Web.

Ferguson, Thomas S. "Game Theory." (n.d.): n. pag. Web. <http://myslu.stlawu.edu/~nkomarov/450/comb.pdf>.

"Theory of Impartial Games." The Mathematics of Toys and Games. N.p.: n.p., 2009. N. pag. Print.