Page:Bouton - Nim.djvu/4

${\frac {2^{n-1}(2^{2n}-1)}{3}}.$

The number of safe combinations in the same case is

${\frac {(2^{n-1}-1)(2^{n}-1)}{3}}$

Hence the chance of a sale combination's being placed upon the table at first is

${\frac {2^{n-1}-1}{2^{n-1}(2^{n}+1)}},$

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

$2^{n}+2+{\frac {3}{2^{n-1}-1}}$ to $1$,

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 12 13 2 14 16 3 14 17 4 18 12
1 14 15 2 15 17 3 15 16 4 19 13
1 16 17 2 18 10 3 18 11 4 10 14
1 18 19 2 19 11 3 19 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 18 13 6 18 14 7 18 15
5 19 12 6 19 15 7 19 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