Arnold--Thanks for the reply. The following might interest you. It's from a book I hope to have publiched shortly. Titled Simply Beautiful, it's a collection of nifty examples of mathematical elegance for people like me, people who are not much good at math, but love it anyway.
Best. Keep in touch.
Steven Goldberg
Chair
Department of Sociology
City College City University of New York
Nim is a game that has been played, in various forms, on at least four continents for at least four centuries. Like tic tac toe, it is a challenging game until one realizes that there is a correct way to play. In the case of tic tac toe, there is a correct way for both players and, if both players make the correct moves, the game must always end in a tie.
In the case of Nim, when one player makes the correct moves, he will always win. (Whether this is the player who goes first or the player who goes second depends on the variation of nim being played.)
Where the perfect strategy for tic tac toe is discoverable by a bright child, discovery of the correct nim strategy takes a mathematical intuition of the highest order for one without mathematical experience.
Nim is often called "The Marianbad Game" because it was played, in its most familiar version and the one given here, in the movie Last Year at Marianbad. In the movie, and traditionally, matches were used, but pencil marks are far more convenient.
The correct Nim strategy is given below. Try playing a few games before looking at the correct strategy. Once you do, you can never again enjoy Nim as a challenging game. On the other hand, in learning the strategy you will experience a deep and, for the mathematically-inclined, exciting glimpse of the deep connections underlying the game.
Notice how all this nicely sums up both the gains and losses that come with modernization. The discovery of the correct strategy for Nim was a solution to a problem that had gone unsolved for centuries. At the same time, the solution meant the loss of a game that had provided pleasure and social contact for millions and had enabled thousands to make a living.
Draw the following layout with a pencil.
l l l l l
l l l l
l l l
l l
l
Two players alternate turns. On each turn a player crosses out marks on one line only. He may cross out as few or many as he wishes, but he must cross out at least one. The player who is forced to cross out the last mark loses.
Notice that position on a line does not matter. For example, if the player going first wishes to take away two marks from line three, it makes no difference whether he takes away, say, the two on the right of line three or the two on the left on line three. Thus, for ease of play it is traditional to take away marks from the right.--so this player would cross out marks indicated by x's.
l l l l l l l l l l x x 1 1 1
[You can also play with piles of pennies. The rule is each player can only take from one pile in any given move. The name of the the game comes from the word nihm, which means take in German. -- agr]
(Read preceding two pages before reading this)
The method works for all forms of NIM.
The 5-4-3-2-1 layout used in this example (the most-commonly-used layout) always results in a win for the player who goes first (assuming that he follows the strategy given).
In the case of some alternative layouts (for example 7-5-3-1), the player who goes second always wins. With such altyernative layouts, the strategy remains the same, simply be certain to let your opponent have the first move. (Nothing he can do can avoid losing.)
Here we also assume that the goal is to force your opponent to cross out the last mark (i.e., the player who crosses out the last mark loses). This is the more-commonly-used method.
If you are playing a variation in which the player who crosses out the last mark wins, simply follow the strategy given, but play to "lose".
Count the number of marks in each row and translate the number to binary:
LAYOUT COUNT DERIVATION OF CODE CODE
l l l l l =5 =1x2^2+0x2+1x1 = 101
l l l l =4 =1x2^2+0x2+0x1 = 100
l l l =3 =1x2+1x1 = 11
l l =2 =1x2+0x1 = 10
l =1 =1x1 = 1
For the moment, simply think of this as a code and ignore its derivation, which you do not need to know in order to win the game. Whenever there are, say, three marks in a row, that row equals eleven. Thus, if the first player crosses out two marks from the top row, the value of the top row goes from 101 to 11.
If you forget the code, you can reconstruct it easily: Begin with 1 match or mark, which equals 1. Two matches or marks will equal the next (ten-base) number that can be made of just 0's and 1's, which is 10. Three matches or marks equals the next (ten-base) number that can be made of just 0's and 1's, which is 11. And so on, to 100 and 101.
Think of the binary numbers not as binary numbers or the count they represent, but as numbers in our ten-based system. Thus, 101 equals one hundred and one, not binary 101 or five. Now:
Always leave your opponent with a total of all even digits (not simply an even number; i.e., 210 is not a good total to leave your opponent with). However, when, at the end of a game, you find that you must leave your opponent with all remaining rows containing only one digit each, leave him with an ODD total). This will always be possible.
Assume you go first. Consider your first move. The total of a full lay-out is 223 (101+100+11+10+1). You want to leave your opponent with 222. (Any other possible total will have an odd digit.) You can cross out one mark in the top row (making 101 become 100), one mark in the middle row (making 11 become 10) or the mark in the bottom row (removing 1). You can not remove, say, one from the second row (making 100 become 1) because the total will then be 124 (which has an odd digit).
To play the game and always win, you need remember or reconstruct the code (lllll=101; llll=100; lll=11; ll=10; l=1.) To see deeply into the structure and beauty of the mathematics, study closely the derivation of the code.