000RM.dvi

17.2 The nim sum of natural numbers 509

17.2 The nim sum of natural numbers ...........

The nim sum of two nonnegative integers is the addition in their base 2
notationswithout carries. If we write

0 0=0, 0 1=10=1, 1 1=0,

then in terms of the base 2 expansions ofaandb,

ab=(a 1 a 2 ···an)(b 1 b 2 ···bn)=(a 1 b 1 )(a 2 b 2 )···(anbn).

The nim sum is associative, commutative, and has 0 as identity ele-
ment. In particular,aa=0for every natural numbera.
Here are the nim sums of numbers≤ 15 :

 0123456789101112131415

0 0123456789101112131415

1 1032547698111013121514

2 2301674510118914151213

3 3210765411109815141312

4 4567012312131415891011

5 5476103213121514981110

6 6745230114151213101189

7 7654321015141312111098

8 8910111213141501234567

9 9811101312151410325476

10 1011891415121323016745

11 1110981514131232107654

12 1213141589101145670123

13 1312151498111054761032

14 1415121310118967452301

15 1514131211109876543210

Theorem 17.3.Suppose two players alternately play one of the counter
gamesG 1 , ...,Gkwhich have Sprague-Grundy sequences(g 1 (n)), ...,
(gk(n))respectively. The player who secures a position(n 1 ,n 2 , ...,nk)
with
g 1 (n 1 )g 2 (n 2 )···gk(nk)=0

has a winning strategy.