Nim Part 2

In the previous post, we discussed the game of Nim. Before we investigate the Mathematics of the game further, we need to introduce an important concept called modular arithmetic. According to Wikipedia, “In Mathematics, modular arithmetic (sometimes called clock arithmetic) is a system of arithmetic for integers, where numbers ‘wrap around’ after they reach a certain value—the modulus.”[1]

Analog clocks use this type of math all the time. If it is 10am and 4 hours pass, what time is it? After some quick mental math, the answer is 2 pm.

Wait a minute, isn’t 10 + 4 = 14?

The key to understanding the enigma is that a clock only has 12 numbers on it. After the little hand passes the 12, it “wraps around” and starts at 0 again. Therefore, we say that a clock has a modulus of 12 or we can say it has “mod 12.”

10 + 4 = 10 + 2 + 2 = 12 + 2

and we know that on a clock the 12 and the 0 are the same thing. So replacing the 12 with a zero, we get

12 + 2 = 0 + 2 = 2

It is like magic the first time you see it, 14 ≡ 2 (mod 12). The triple equals sign signifies that 14 and 2 share some commonality but are not the same number. The “mod 12” signifies that we are working with a system that has 12 steps before wrapping around (12 numbers on a clock).

This same math is all around us. When we go from week to week, we add 7 days but do not change the day of the week. When we go month to month, we reuse the days of the month. Using real world examples can be helpful to get an intuitive grasp of the underlying math but it is not very useful for actual calculations. For example, what number would the little hand on the clock read after 2043 hours? If you were to spin the little hand around and around you would be here forever. The mathematical solution is much more elegant.

Each time the little hand performs 1 revolution it goes through 12 numbers. Thus, 0 ≡ 12 (mod 12), 12 ≡ 24 (mod 12), 0 ≡ 240 (mod 12) and so on. This means that every multiple of 12 will leave the clock unaffected since it will return the hand back to where it started. Therefore, what we really are looking for is the remainder in the math problem of 2043 ÷ 12.

When we take our 2043 and divide by 12 (using our old friend, long division), we get 170 and remainder 3.

Thus 2043 ≡ 3 (mod 12).

I hope the above is clear, if not it would be best to try your hand at a couple of examples. Convince yourself that with modulus 12,

25 ≡ 1 (mod 12), 38 ≡ 2 (mod 12), 100 ≡ 4 (mod 12).

If we mix it up a bit and use 3 as the modulus, then

3 ≡ 0 (mod 3), 10 ≡ 1 (mod 3), 14 ≡ 2 (mod 3), and 502 ≡ 1 (mod 3).

Returning to the game of Nim with our new-found powers of modular arithmetic, we can be more precise about the game. We found that the bad piles were 3, 6, and 9. These are all multiples of 3. Using the language of modular arithmetic, we can see that:

3 ≡ 6 ≡ 9 (mod 3)

The piles with 3, 6, and 9 are all the same mod 3. Whenever 3 stones are removed from the game, poor Bob is back where he started, in a losing position.