Nim

Nim

The game of Nim has origen in China, although not by this name. It was played in Europe as of the XVI century. Played with stones, coins, matches or any small object that exists in individual units. An arbitrary number of piles of these objects are formed, usually between three and six piles of from one to around twenty objects. A move consists of removing any number whatsoever (greater than zero) of objects from one of the piles. The player who wins is who takes the last object away. We see that Nim is impartial: there is no difference between being the first or second player, it mattering only who is the next to play. This will mean that the values of configurations will be zero or fuzzy, the fuzzy values being what is called surreal.

Suppose there are n piles of toothpicks, with p1 toothpicks in the first pile, p2 in the second pile, ..., pn in the n-th pile. At the end of the game nothing will remain and the value is zero. Observe that by our system of calculation this configuration has the value { | } or, if you prefer, { ? | ? }. So, in the informal sense we used above, we are saying the most simple number less than no specific number and greater than another is zero. This rather obtuse idea will be explained in more detail further on. For readers who have not seen these ideas before, consult Mathematical Games.

Now consider the configuration that consists of one pile of one toothpick. A and B have the same options, as always in impartial games, to retire this same toothpick. As the empty table, as seen above, has value zero, on doing the calculation of value we have { 0 | 0 }. What value is this? Evidently there is no real number that is simultaneously greater than and less than zero. So this value is not a real number; as in this case the first to play always wins, we see that in the table given above the value should not be neither positive nor negative, but fuzzy. This surreal number is designated *1, and is considered near zero but neither less than nor greater than zero. That is exactly the intention of the name: fuzzy.

A single pile of two toothpicks will permit two distinct moves for either A or B: the removal of one or two toothpicks. These moves result in configurations of values *1 and zero respectively. Thus the value of a pile of two is { 0, *1 | 0, *1} = *2. In general a pile of n toothpicks will have value { 0, *1, *2, ..., *(n-1) | 0, *1, ..., *(n-1) } = *n. Observe that the value is always the first fuzzy value that is not contained between brackets. That may sound trivial, but it is in fact a general rule called the rule of minimum excluded, or mex.

If instead we have two separate piles it isn't much harder. Two equal piles give certain victory to the second to play: whatever the first player does, she simply imitates the first player's move, thus maintaining after her move two equal piles. In terms of values, this implies that *k + *k = 0. Similarly, if we have two unequal piles the first to play guaratees his win by leaving after his move two equal piles.

Figure-1

Three piles, of one, two and three toothpicks respectively, implies in the loss of whoever begins the game, for whatever the first player plays, the second player can also create two equal piles after her move. Thus *1 + *2 + *3 = 0, and in consequence of this, *1 + *2 = *3, *1 + *3 = *2 and *2 + *3 = *1.

Charles L. Bouton published an article in 1901 which clarified once and for all the game (in fact, the name Nim was his invention). His method consisted of writing the number of toothpicks in each pile in binary notation: every whole number can be written using the numerals 0 and 1, expressing n as a sum of powers of two.

For example, 13 written in binary notation is 1101 = 1 x 23 + 1 x 22 + 0 x 21 + 1 x 20. Now suppose we have two piles with n1 and n2 toothpicks. Writing n1 and n2 in binary notation, one above the other, we see that if they are equal there will be an even number of ones in each column. Thus after one player reduces one pile, altering the ones in a column, the second player may reciprocate restoring an even number on ones in each columns by returning to a situation of two equal piles.

That idea generalizes. Consider three piles as above, with one, two and three toothpicks in each pile. Writing in binary notation one above another we have

10
11
1

and we have an even number of ones in each column. As a given move by a player alters only one of the piles (numbers), whatever a player may do in this situation will leave an odd number of ones in at least one column. The second player restores the even number, and the game continues in this way until it ends – with victory for the second player. Bouton proved that if the number of ones in each column is even, victory is guaranteed for the second player (if she commits no errors!). Bouton considered sum of two ones or two zeros as zero, and sum of zero and one as equal to one. In this sense, specifically, he proved that

i) victory corresponds to sum zero;
ii) if a sum is zero, the next move will certainly yield a non-zero sum;
iii) if the sum is not zero, there always exists a move to make the sum after the move equal to zero.

To understand the facts ii) and iii), consider a situation of sum zero. For example, let there be four piles of 5, 2, 10 and 13 toothpicks. When written in binary notation we have 101, 10, 1010 and 1101. The sum is zero:

101
10
1010
1101
0000

Independently of what the next move is, one of the 0's or 1's will be altered, so that the number of 1's in at least one of the columns will no longer be an even number. Finally, consider the game with piles of 6, 3, 8 and 9 toothpicks. Writing the four numbers in binary notation we have

110
11
1000
1001
0100

Whoever plays first will certainly be able to change things so that there are an even number of ones in each column. Taking four toothpicks from the first pile will have that effect, leaving two in the pile with sum:

10
11
1000
1001
0000

The most important aspect of this idea is that it functions in many other games besides Nim. However, for pedagogical purposes we must ask how to use the analysis in activities of Nim from early on at school until the end of high school.

For that we have a pratical method, without an absolute guarantee, but frequently useful. Suppose for example the challenge of playing against an opponent a match with three piles of 4, 7 and 13 toothpicks. Instead of making a formal analysis via binary notation (but remembering the basic idea) we observe that only one pile has more than 8 toothpicks and therefore for certain the sum of the piles is non null. That means that the first to play can guarantee victory, but rather than doing the exact calculation of a winning move we simply reduce the pile of 13 to one of 5 or 6 (so that there are not two equal piles after our move). Let's say five and now considere the match from the second player's point of view.

With piles of 7, 5 and 4 matches the simplest logic says: all piles are smaller than 8. Therefore one should move so as to not produce two equal piles. In fact one of these moves – reducing the pile of four to one of two toothpicks, guarantees victory.

In 1910 the mathematician Moore proposed an alternative game to Nim, called Nimk, and published an article with respect to strategies of play. Nimk resembles Nim with the following difference: instead of taking any number of toothpicks from one pile, in Nimk we may remove any (same) number of toothpicks from one to k piles simultaneously. Consider Nim2 as an example. In this game one may remove any number of toothpicks from one or two piles simultaneously, always the same number of toothpicks from each pile.

Como é o Nimk no caso de haver somente duas pilhas?

      
Figure-2

In Nimk, as soon as there are only two piles, victory is guaranteed for the next player to move. The first strickly “non-trivial” game is one of three piles of one toothpick each – with certain victory for the second to play. In general the analysis is similar to that of Nim: express the number of toothpicks in each pile in binary notation and sum the columns, but sum them mod k+1 e not mod 2 (as in Nim). If the sum is zero there is victory guaranteed for the second player to move. If not, the first player may win by moving so as to make the sum after his move equal to zero (mod k+1).

For example, in Nim2 (with k+1 = 3), suppose we begin with four piles of 3, 6, 7 and 10 toothpicks respectively. Summing mod 3 we have

11
110
111
1010
1212

Thus the first to play can guarantee victory. We leave it to the reader to deduce which move will have this effect.