Nim and simple mathematical proofs 1/3

A few weeks ago I discussed a game called Nim. In studying Nim, with the help of Thomas S. Ferguson’s book Game Theory, I have again found great joy in mathematical thinking, proving theorems and using logical thinking to come to conclusions.

Many people, as far as I know, have some kind of fear of mathematics and mathematical notation. Some people are even proud of their mathematical illiteracy, which is odd, considering that nobody boasts how their Spanish or Chinese skills are non-existent. Working with games and proofs, like those required by Nim, might help people see the value and true beauty of mathematical thinking. People might understand that extensive mathematical notation is not always necessary to prove mathematical theorems, and that mathematical notation is actually just another language that helps us formulate and formalize logical thinking, removing all ambiguity. In this post and two additional ones I will present three proofs related to Nim to show you, how mathematical thinking can be used quite cleverly to show interesting facts.

Bouton’s theorem

In his 1902 article Nim, a game with a complete mathematical theory in Ann. Math. 3, 35-39

L. Bouton proves the following theorem (Theorem 1, Bouton’s theorem): “In a game of Nim a position is a P-position if and only if the Nim-sum of its components is zero.”

A Nim-sum is calculated as follows:

  • The number of sticks in each pile is expressed in base two.
  • These figures are added without carry, so that the sum of each column is 1, if the column contains an odd number of ones. Otherwise, the sum of that column is 0.
  • The Nim-sum is zero when the sum of each individual column is 0.

As an example of calculating the Nim-sum we take three piles with 4, 5, and 8 sticks respectively. The Nim-sum of these piles in base two is:

1000
1010
1000
1001

The result, in base 10, is 9. Since this Nim-sum is non-zero, according to Bouton’s theorem this would be an N-position. It is worth noting that a Nim-sum of two identical positive integers is also zero due to the definition of Nim-sum. Nim-sum is also associative and commutative and 0 is an identity for addition. (see Ferguson’s Game Theory, Part 1, Chapter 1, page 10)

Proving Theorem 1

Proving Bouton’s theorem is partially a constructive proof, relying on the definitions of P- and N-positions. The claim of the theorem is compared against these definitions to show that they are equal. We recall that P- and N-positions are defined as follows:

  • The terminal position is a P-position.
  • An N-position is such that there is at least one possible move into a P-position.
  • A P-position is such that from it is possible to move only into an N-position.

Now we just have to show that the terminal position has a Nim-sum of zero, a P-position always has a Nim-sum of zero and that a Nim-sum of zero is never an N-position. If we can prove this, we will have proven Bouton’s theorem.

Let’s start by observing that the terminal position has a Nim-sum of zero, so condition 1 is fulfilled.

For condition number 2 we can construct such a move, where we can move from a position with a non-zero Nim-sum (a purported N-position) into a position with a Nim-sum of zero (a purported P-position). In our example we do this by reducing the number of ones in the leftmost column with an odd number of ones (the 4th column) so that each column will eventually contain an even number of ones. In our case, there is only one potential move, since there is only one number one in the leftmost column. Thus, the only move into a P-position is to remove 7 sticks from the pile of 8. By this example we see, that we can move from an N-position into a P-position, so condition 2 is also fulfilled. For a more formal and generalized proof for this part, see Bouton’s original article.

The third condition can be shown to be true by the following reasoning. If we are in a position with a Nim-sum of zero, removing any number of sticks from any pile will leave us witha non-zero Nim-sum (a purported N-position). This is because if we remove any number of sticks from a pile, the number of sticks in all the other piles remains the same. If the Nim-sum of the new position were zero, it would imply that the number of sticks remaining in the pile, from which sticks were removed, has stayed the same, but this is a contradiction. Thus, condition 3 also holds.

Collecting together the proofs for conditions 1, 2 and 3 we have shown the following:

  • The terminal position has a Nim-sum of zero.
  • From a position with a non-zero Nim-sum we can move into a position with a Nim-sum of zero.
  • From a position with a Nim-sum of zero it is possible to move only into a potision with a non-zero Nim-sum.

We see that these statements are analogical to conditions 1, 2 and 3 and that a position is a P-position if and only if the Nim-sum of that position is zero.

I hope this post gave you an idea of how simple logical thinking with quite elementary mathematical notation can provide a powerful tool for analyzing problems. In my next post I will discuss a Nim variant called Nimble and show how Nim can come in disguise.

Leave a Reply

Your email address will not be published. Required fields are marked *