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 *P*_{1},
*P*_{2}, ... *P*_{k} 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(P_{1}), ... G(P_{k}) 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(P_{s}) (i.e. obtained by writing the
G(P_{s}) 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*(*P*_{s}), as the opponent can restore the *status
quo*. And if only decreases in *G*(*P*_{s}) 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*(*P*_{s}) for the component
positions. Nim is an example; a heap *H*_{x} of
*x* counters constitutes a component position, since each
player in turn alters one heap only, and *G*(*H*_{x}) = *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*(*H*_{3}) = 1. Generally *G*(*H*_{x}) in
Grundy's game is the least integer different from all nim-sums of *G*(*H*_{y}) and
*G*(*H*_{x-y}), 0 < *y* < ½*x*.
The series goes

x = 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |

G(H_{x}) = 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 *R*_{x} 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 *R*_{1} (= a single counter standing on
its own). The *G*(*R*_{x}) 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

About Eureka Online

Contact: The Archimedeans (Eureka Online) (archim-eureka-online@srcf.ucam.org)

Online HTML version last updated: 3 March 2004