17.1 Subtraction games 503
17.1.1 The Sprague-Grundy sequence
LetGbe a 2-person counter game in which two players alternately re-
move a positive amount of counters according to certain specified rules.
The Sprague-Grundy sequence ofGis the sequence(g(n))of nonnega-
tive integers defined recursively as follows.
(1)g(n)=0for allnwhich have no legal move to another number.
In particular,g(0) = 0.
(2) Suppose from positionnit is possible to move to any of positions
m 1 ,m 2 , ...,mk, (all<n), theng(n)is the smallest nonnegative integer
different fromg(m 1 ),g(m 2 ), ...,g(mk).
Theorem 17.2.The player who secures a positionnwithg(n)=0has
a winning strategy.
Example 1: the trivial counter game
IfGis the game which the players may subtract anypositiveamount, the
Sprague-Grundy sequence is the natural sequence
0 , 1 , 2 , 3 , ..., n,....Example 2: removing not more thandcounters
IfGis the game which subtracts numbers<d, then the Sprague-Grundy
sequence is periodic 0 , 1 , 2 ,...,dā 1. The values ofnfor whichg(n)=
0 are precisely the multiples ofd.