The Archimedeans - Why are Series Musical?

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 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 P₁, P₂, ... P_k 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(P₁), ... 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₃) = 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:

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 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₁ (= 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):

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 , 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.