Why are Series Musical?

ASKS BLANCHE DESCARTES

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 \Gamma 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 [\Omega(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 0 <= r < G(P) 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 \Gamma_1, \Gamma_2, ... \Gamma_k 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 \Gamma_1, \Gamma_2, ... \Gamma_k. 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 >= 0 different from all nim-sums of G(Hy) and G(Hx-y), 0 < y < ½x. The series goes

x = 0123456789101112
G(Hx) = 0001021021021

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:

FIG. 1.: Dividing heaps in different parts, different parts - not the easiest of the arts: No, no, no (just you try) No! No! No!!

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):

FIG. 2.: .6 WALTZ: If I'm alone, all on my own, there I must always stay.  But if I touch another such, // I may be taken away.  And as a boon, this little tune shows you the right move to play.

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:

FIG. 3.: This series still quite baffles me.  The general term I cannot see.  P'rhaps it just wanders along aimlessly.

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 x >= 54, and Kayles, remove 1 or 2 adjacent counters, has exact period 12 for x >= 71. 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.


Additional notes to the online version

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