NIM, A GAME WITH A COMPLETE MATHEMATICAL THEORY.
By Charles L. Bouton.
The game here discussed has interested the writer on account of its seeming complexity, and its extremely simple and complete mathematical theory.[1] The writer has not been able to discover much concerning its history, although certain forms of it seem to be played at a number of American colleges, and at some of the American fairs. It has been called Fan-Tan, but as it is not the Chinese game of that name, the name in the title is proposed for it.
1. Description of the Game. The game is played by two players, A and B. Upon a table are placed three piles of objects of any kind, let us say counters. The number in each pile is quite arbitrary, except that it is well to agree that no two piles shall be equal at the beginning. A play is made as follows:—The player selects one of the piles, and from it takes as many counters as he chooses; one, two, . . ., or the whole pile. The only essential things about a play are that the counters shall be taken from a single pile, and that at least one shall be taken. The players play alternately, and the player who takes up the last counter or counters from the table wins.
It is the writer's purpose to prove that if one of the players, say A, can leave one of a certain set of numbers upon the table, and after that plays without mistake, the other player, B, cannot win. Such a set of numbers will be called a safe combination. In outline the proof consists in showing that if A leaves a safe combination on the table, B at his next move cannot leave a safe combination, and whatever B may draw, A at his next move can again leave a safe combination. The piles are then reduced, A always leaving a safe combination, and B never doing so, and A must eventually take the last counter (or counters).
2. Its Theory. A safe combination is determined as follows: Write the number of the counters in each pile in the binary scale of notation,[2] and
- ↑ The modification of the game given in §6 was described to the writer by Mr. Paul E. More in October, 1809. Mr. More at the same time gave a method of play which, although expressed in a different form, is really the same as that used here, but he could give no proof of his rule.
- ↑ For example, the number 9, written in this notation, will appear as
