in
which 2 players move alternately, and the last player wins (moving to
a "terminal position"). Define inductively a function
G(P) of the position P [
in Grundy's Paper] as
follows:-MOST mathematicians know the theory of the game of
Nim, described in books on mathematical recreations. But few seems to
be aware of Dr. P. M. Grundy's remarkable generalisation, published in
Eureka, 2, 6-8 (1939).
Consider a game in
which 2 players move alternately, and the last player wins (moving to
a "terminal position"). Define inductively a function
G(P) of the position P [ in Grundy's Paper] as
follows:-
| (a) | if P is terminal, G(P) = 0, |
| (b) | if there are permitted moves from P to Q, from P to R, from P to S, and so on, then G(P) is the least non-negative integer different from all of G(Q), G(R), G(S), etc. |
It follows that if 
there is a move from P to some
R with G(R) = r, but no move to any
position U with G(U) = G(P). If
positions P with G(P) = 0 are called
"safe," the winning strategy is to move always to a safe position:
either this is terminal, and wins immediately, or the opponent moves
to an unsafe position and the cycle repeats.
Now imagine the players engaging in a "simultaneous display" of
k games 
, 
, ... 
of this sort, the rule being
that each player in turn makes a move in one and only one game, or if
he cannot move in any game he loses. Let P1,
P2, ... Pk be the positions in the
respective games , , ... . Then
Grundy's Theorem states that -
| (i) | this combined position is safe if and only if k heaps of G(P1), ... G(Pk) counters respectively form a safe combination in Nim, |
| (ii) | more generally, the G function of the combined position is the "nim-sum" of the separate G(Ps) (i.e. obtained by writing the G(Ps) in the scale of 2 and adding columns mod 2). |
For no player can gain any advantage by moving so as to increase any G(Ps), as the opponent can restore the status quo. And if only decreases in G(Ps) are considered, the game is identical with Nim, thus proving assertion (i). Therefore G(P) = g if and only if the combined position (P, P') is safe, where G(P') = g. From that (ii) follows fairly readily.
It follows that we can analyse any such combined game completely,
provided that we can find the G(Ps) for the component
positions. Nim is an example; a heap Hx of
x counters constitutes a component position, since each
player in turn alters one heap only, and G(Hx) = x.
Many variants of Nim are similarly analysed. Less trivial is Grundy's
game, in which any one heap is divided into two unequal (non-empty)
parts. Thus heaps of 1, 2, are terminal, with G = 0, a heap of 3 can
only be divided into 2 + 1, which is terminal, so
G(H3) = 1. Generally G(Hx) in
Grundy's game is the least integer 
different from all nim-sums of G(Hy) and
G(Hx-y), 0 < y < ½x.
The series goes
| x = 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| G(Hx) = 0 | 0 | 0 | 1 | 0 | 2 | 1 | 0 | 2 | 1 | 0 | 2 | 1 |
continuing with 3, 2, 1, 3, 2, 4, 3, 0, 4, 3, 0, 4, 3, 0, 4, 1, 2, 3, 1, 2, 4, 1, 2, 4, 1, 2, ... This curious "somewhat periodic series" seems to be trying to have period 3, but with jumps continually occurring. Mr. Richard K. Guy confirmed this up to x = 300. He suggested that it might be played on a piano, taking 0 to be middle C, 1 = D, 2 = E, etc. The inner meaning then became evident:
Guy also worked with rows Rx of x counters, in which certain sets of consecutive counters could be extracted (thus possibly leaving two shorter rows, one each side of the extracted set). In his ".6" game, any one counter can be removed, except an R1 (= a single counter standing on its own). The G(Rx) series (x = 1, 2, ...) is a waltz (N.B. some notes span two bars):
But at this point the tune completely broke down. I asked Guy if he could think of any reason for that: he said, "Yes, an error I made in the calculation." After correction the waltz proceeds:
This tries to be periodic with period 26, but jumps keep appearing.
Many other such games give tuneful, somewhat periodic series, for no
evident reason. Guy discovered two curious exceptions: his
".4," remove 1 counter not at the end of a row, has exact
period 34 for 
, and
Kayles, remove 1 or 2 adjacent counters, has exact period 12 for
. Thus these games
have a complete analysis. But generally it might be helpful to bring
in a professional musician to study number theory. Perhaps a thorough
study of Fermat's Last Theorem will uncover the Lost Chord. After
all, why not?
Eureka, 16.
Reproduced from Eureka 27 pages 29-31.
HTML conversion Copyright © 2002-4 The Archimedeans.
Erratum: "few seems to be aware" should read "few seem to be aware".
Extensive computations have so far failed to provide a complete analysis of Grundy's game or .6.
Return to Eureka 27 home page
Return to Eureka home page
Return to Archimedeans home page