Nim, A Game with a Complete Mathematical Theory
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. 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, and place these numbers in three horizontal lines so that the units are in the same vertical column. If then the sum of each column is 2 or (i. e. congruent to 0, mod. 2), the set of numbers forms a safe combination. For example,
1 0 0 1,
1 0 1,
1 1 0 0,
or 9,5,12 is a safe combination. It is seen at once that if any two numbers be given, a third is always uniquely determined which forms a safe combination with the two given numbers. Moreover, it is obvious that if a,b,c form a safe combination any two of the numbers determine the remaining one, that is, the system is closed. A particular safe combination which is used later is that in which two piles are equal and the third is zero. In the proofs which follow, the binary scale of notation is used throughout.
Theorem I. If A leaves a safe combination on the table, B cannot leave a safe combination on the table at his next move. B can change only one pile, and he must change one. Since when the numbers in two of the piles are given the third is uniquely determined, and since A left the number so determined in the third pile (i. e., the pile from which B draws) B cannot leave that number. Hence B cannot leave a safe combination.
Theorem II. If A leaves a safe combination on the table, and B diminishes one of the piles, A can always diminish one of the two remaining piles, and have a safe combination. Consider first an example. Suppose A leaves the safe combination nine, five, twelve, and that B draws two from the first pile, leaving the numbers seven, five, twelve, or
1 1 1,
1 0 1,
1 1 0 0.
If A is to leave a safe combination by diminishing one of the piles, it is clear that he must select the third pile, that containing twelve. The number which is safe with 111 and 101 is 10, or two. Hence A must leave two in the pile which contains twelve, or draw ten from that pile, and by doing so he leaves a safe combination.
To prove the general theorem, let the numbers, expressed in the binary scale, be written with the units in a vertical column, and suppose that A left a safe combination. B selects one of the piles and diminishes it. When a number of the binary scale is diminished it is essential to notice that in going over the number from left to right the first change which occurs is that some 1 is changed to 0, for if a 0 were changed to 1 the number would be increased whatever changes were made in the subsequent digits. Consider, then, this first column, counting from the left, in which a change occurs. One and only one of the other two numbers will contain 1 in this same column, for A left a safe combination. Let A select the pile which contains the 1 in this column, and change the number by writing in this column, and filling the remaining columns to the right with or 1 so as to make a safe combination. The columns to the left remain unchanged, since they already have the required form. The new number so formed will be less than that in the pile which A selected. Hence whatever B draws, A can always diminish one of the piles, and leave a safe combination. That is, if A at any play can leave a safe combination on the table, he can do so at every subsequent play, and B never can do so.
If the play continues in this way A must win. For one of the piles must be reduced to zero by either A or B. If B reduces it to zero, the two remaining piles will be unequal, since B can never leave a safe combination, and A at his next move will make them equal, and will thereafter always leave them equal. B must, therefore, reduce the second pile to zero, and A then takes all of the third pile, and wins. If, on the other hand, A is the first player to reduce one of the piles to zero, he leaves the other two piles equal and wins as before. Hence we see that the player who can first leave a safe combination on the table should win.
If it happens that in the beginning a safe combination is placed on the table, the second player should win. If in the beginning a safe combination is not placed on the table, it is easily seen that the first player can always leave a safe combination by diminishing some one of the piles, and he can often do this by drawing from either one of the three piles. Therefore in this case the first player should win. That is, the first player should win or lose according as a safe combination is not or is placed on the table at the beginning.
3. The Chance of a Safe Combination. Assuming that the number in each pile at the beginning was determined by chance, let us compute the chance of a safe combination's being placed upon the table. It is easily shown that if each pile contains less than counters and if no pile is zero (i. e. if there are three piles), the possible number of different piles is
The number of safe combinations in the same case is
Hence the chance of a sale combination's being placed upon the table at first is
and this is the chance that the second player should win. The chances of the first player's winning are to those of the second as
on the assumption that both players know the theory, and that the numbers in the various piles were determined by chance.
4. A List of Safe Combinations, n = 4. The following are the 35 safe combinations all of whose piles are less than 16:
1 2 4 6 3 4 7 4 8 12
1 4 5 2 5 7 3 5 6 4 9 13
1 6 7 2 8 10 3 8 11 4 10 14
1 8 9 2 9 11 3 9 10 4 11 15
1 10 11 2 12 14 3 12 15
1 12 13 2 13 15 3 13 14
1 14 15
5 6 8 14 7 8 15
5 9 12 6 9 15 7 9 14
5 10 15 6 10 12 7 10 13
5 11 14 6 10 13 7 11 12
Of course, to give all safe combinations of numbers less than 16 we should have to add to the above table the 15 of the form 0,n,n.
5. Generalization. The foregoing game can be at once generalized to the case of any number of piles, with the same rule for playing. In this case a safe combination is a set of numbers such that, when written in the binary scale and arranged with the units in the same vertical column, the sum of each column is even (i. e., ≡ 0, mod. 2). Just as before, it is shown that the player who first leaves a safe combination can do so at every subsequent play, and will win. The induction proof is so direct that it seems unnecessary to give it.
6. Modification. The game may be modified by agreeing that the player who takes the last counter from the table loses. This modification of the three pile game seems to be more widely known than that first described, but its theory is not quite so simple.
A safe combination is defined just as in the first case, except that 1,1,0 is not a safe combination, and 1,1,1 and 1,0,0, are safe combinations. When the first theory indicates that A should play 1,1,0 he must play either 1,1,1 or 1,0,0. The earlier part of the proof proceeds as before. In order to complete it, we must show that B can never leave 1,1,1; that, when 1,1,0 is indicated for A, he can always play either 1,0,0 or 1,1,1; and finally that, if the play is carried out in this way, B must take the last counter. That B can never leave 1,1,1 is at once clear, for A never leaves 1,1,n where n > 1, since this is not a safe combination. Secondly, let us consider what sets of numbers B can leave which would indicate 1,1,0 as A's next play in the first form of game. They are 1,1,n where n > 1, and 1,n,0 where n > 1. In the first case A leaves 1,1,1 and in the second 1,0,0. The proof is now easily completed. Either A or B reduces a pile to zero. If B does so, the other two piles are unequal and both greater than unity, or at least one of the two remaining piles is unity. In the latter case A obviously wins. In the former case A makes the two piles equal, and then keeps them equal until B reduces one of them to 1 or 0. If B makes it 1, A takes all the other pile; if B makes it 0, A takes all but 1 of the other pile. Hence if B first reduces a pile to zero A wins. If A first reduces a pile to zero he leaves the other two piles equal and each greater than unity, and wins as before. Hence if A plays on the safe combinations as here modified, B must take the last counter from the table, and loses. That is, in this modified game, also, the player who can first get a safe combination should win.
This modified game can also be generalized to any number of piles. The safe combinations are the same as before, except that an odd number of piles, each containing one, is now safe, while an even number of ones is not safe.
- 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
- The proof of this statement depends on the fact that the number 100 . . . (n ciphers), or , is greater than the number 11 . . . (n ones), or .