Nimbers, the numbers for Nim game

If you are in Hong Kong and you need help for university mathematics courses, please visit www.all-r-math.com.

In previous posts, we have introduced some simple games. One of them is $G'(n)$, which consists a board with n pieces, two players in turn can take any number of pieces from the block, the winner is the one who takes the last piece.

Looks like a stupid game, right? The first player can take all pieces at his first step and win.

How about G'(3)+G'(7)? G'(2)+G'(6)+G'(5)? G'(11)+G'(6)+G'(8)+G'(3)?

Not so easy now. It is the famous Nim game. Some says that Nim originated from China, but no one can sure.

** ****** *****

The Nim game G'(2)+G'(6)+G'(5) consists of three heaps, each time a player can take away any number of pieces from a heap, the objective is to take the last piece.

To solve Nim, mathematicians have introduced the concept of nimber, which is basically ordinal numbers represented in binary numeral system under the position-wise boolean addition (i.e. 0+0=1+1=0, 0+1=1+0=1).

For example 3+7=(011)+(111)=(100)=4, 5+11=(0101)+(1011)=(1010)=10.

There is also nimber multiplication, which is omitted here.

Before we get into the relation between Nim and nimber, lets investigate the properties of nimber addition:

1. n+m=0 if and only if n=m
2. If n has a 1 at the 2^k-th position and m is a k-digit nimber, then n+m<n. (The proof is easy: (1...1...)+ (1...)=(1...0...)<(1...1...). )
3. If the nim sum of several nimbers is a k-digit nimber, then at least one nimber has a 1 at the 2^k-th position.
4. If the nim sum of several nimbers is 0, then replace any one of them by a different nonzero nimber, the new nim sum is nonzero. (Proof: Given n₁+n₂+...+n_r=0. Suppose we replace the first nimber by m, then m+n₂+...+n_r=m+n₁+n₁+n₂+...+n_r=m+n₁≠0.)

Now we are ready to study Nim.

For each heap, there are a nimber of pieces. Take the nim sum of the nimbers.

** ****** *****

The Nim sum of G'(2)+G'(6)+G'(5)is 2+6+5=(010)+(110)+(101)=(001).

The objective of the game is to take away all the pieces. At that last moment, the number of pieces is 0. From Property (4), if the nim sum is already 0, take away any number of pieces from a heap cannot keep the nim sum be 0, and therefore cannot win the game.

What if the nim sum, say m is a k-digit nimber?
From Property (3), there is a heap of which the nimber, say n, has a 1 at the 2^k-th position. From Property (2), n+m<n. Take away some pieces fromt that heap so that there are n+m pieces left. The nim sum becomes
nim sum of all other heaps+(n+m)=(m-n)+(n+m)=m+m=0.

Therefore, the winning strategy is to maintain the nim sum to be 0. If the nim sum at the beginning is 0, the second player wins; if the nim sum at the beginning is nonzero, the first player wins.

Consider the game G'(2)+G'(6)+G'(5).
2=(10), 6=(110), 5=(101).
2+6+4=(10)+(110)+(100)=(001).
Only 5 have a 1 at the 1-th position. (101)+(001)=(100)=4, so the player has to left 4 in the last heap.

The game becomes G'(2)+G'(6)+G'(4).
The nim sum is 0. No matter the opponent does, he will disturb the balance. Suppose he takes away 3 pieces from the second heap.

The game becomes G'(2)+G'(3)+G'(4).
The nim sum is (101). The player now leaves (100)+(101)=(001)=1 pieces in the last heap.

The game becomes G'(2)+G'(3)+G'(1).

I suppose the readers can figure out the rest.