|
Kayles
Conway describes normal play Kayles on pg 127 of On Numbers and Games,
Academic Press, 1976:

Kayles is the octal game 0.77. It was first completely
solved in normal play by Richard Guy,
and by Sibert and Conway for misère play.
Normal Play Nim Sequence
0 1 2 3 4 5 6 7 8 9 10 11
----------------------------------
0+ 0 1 2 3 1 4 3 2 1 4 2 6
12+ 4 1 2 7 1 4 3 2 1 4 6 7
24+ 4 1 2 8 5 4 7 2 1 8 6 7
36+ 4 1 2 3 1 4 7 2 1 8 2 7
48+ 4 1 2 8 1 4 7 2 1 4 2 7
60+ 4 1 2 8 1 4 7 2 1 8 6 7
72+ 4 1 2 8 1 4 7 2 1 8 2 7
The Kayles nim sequence is periodic of length 12the values in
final row of the table repeat themselves indefinitely.
Sibert-Conway Decomposition for Misère Play
The surprising solution to the misère version of Kayles was discovered
by the amateur William L. Sibert in 1973, but it was not published
until over seventeen years later. There's an interesting story behind
these events. In 1989,
Sibert wrote a description of his solution and a proof in
an unpublished 43 page document entitled
The Game of Misere Kayles: The "Safe
Number" vs "Unsafe Number" Theory.
Sibert wrote the following
"Preamble" to this document:
Some years ago (about 1961) I was stumped by a problem in an old
puzzle book (possibly by Dudeney). It described the plight of
a group of tourists in the Alps who were consistently defeated
by a young Swiss miss at a pluck-the-petals-from-the-daisy type
of game.
Two players took turns plucking petals, and the game required
each player to take either one or to petals at a time ... with the
proviso that if two petals were taken, they had to physically
adjacent.
The winner was the player who took the last petal, and, according
to the author, the young lass always won ... whether she played
first or second.
The "solution" given in the back of the book described her strategy
as one of presenting her opponent with a daisy which had been divided
into two identical segments. She then simply matched her opponent's
play each time, usng the sector opposite the one into which the opponent
had just played.
This struck me as an unsatisfactory answer, in that she had to rely
on inept play by her opponent in those cases where she played first.
This led me, for some reason, to try and find the winning strategy
for a re-defined game in which the wind had randomly blown away
a number of petals from a large daisy before the game began.
(It was only much later that I learned that the problem I had set for
myself was to find the solution to the well-known [normal play]
game "Kayles".)
After many, many, many hours of work, I had the strategy for all possible
games in which the largest unbroken string of petals was 168 or less...
and was satisfied that this strategy could be applied to any game with a string
or strings exceeding 168. (I could have stopped at 166, but did the next
two numbers just to round out a final cycle of 12).
The work was done on a commuter train, returning home from work in the
evenings, and I used worksheets which bore a crude resemblance to the
Grundy scale described in "Winning Ways" ... except that my worksheets
didn't "slide". A copy of one of those worksheets is attached, as
Appendix IV.
Having solved the problem, I forgot about it until I happened to see
a Martin Gardner column in an issue of Scientific American in which he
discussed Kayles. The issue came out in 1969 or 1970, and, as I
recall, his number values matched mine exactly, except for one
number (28 ?). I rechecked by calculations, and concluded that the
variance was almost certainly caused by a "typo" in the article. Many
years later, when I acquired a copy of "Winning Ways" my values were
confirmed as correct.
In any case, reading the Gardner article reawakened my interest in
Kayles, and I set out to try and solve the problem of the Misere version
of the game.
In time, I developed the theory of "Safe" and "Unsafe" numbers ...
and by 1973 I had what I believed was a general solution to the game.
Again, I set the matter aside, but for some reason in 1979 I sent
an outline of my solution to Mr. Gardner, asking him whether it was
correct. He replied that he didn't know, and suggested that I check
with Professor Guy.
Once more I let matters slide, but in 1989 I finally sent the "solution"
to Professor Guy, and asked for his reaction. The subsequent
exchange led me to assemble my work papers into what I trust is
a coherent document. What follows is the document wich I hope will
confirm, under scrutiny, that my theory is correct.
Here is the solution:
PN Positions
E(5) E(4,1)
E(17,12,9) E(20,4,1)
25 E(17,12,9) D(20,4,1)
NP Positions
D(5) D(4,1)
E(5) D(4,1)
E(4,1) D(9)
12 E(4,1)
E(17,12,9) D(20,4,1)
25 D(9) D(4,1)
|