Page:Bouton - Nim.djvu/3

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.^[1] 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 $\scriptstyle 2^{n}$ counters and if no pile is zero (i. e. if there are three piles), the possible number of different piles is

---

1. The proof of this statement depends on the fact that the number 100 . . . (n ciphers), or $\scriptstyle 2^{n}$, is greater than the number 11 . . . (n ones), or $\scriptstyle 2^{n-1}+2^{n-2}+\dots +2+1=2^{n}-1$.