Newsgroups: sci.math
From: hoey@pooh.tec.army.mil (Dan Hoey)
Date: 1997/02/22
Subject: Re: 15-coins game [spoiler]

[ This is a revised version of an article I sent last night.  That
  version seems to have evaporated. ]

David Madore <mad...@clipper.ens.fr> writes:

of a game on a row of coins, in which a move consists of selecting a
consecutive subsequence of coins, provided that the rightmost coin
of the subsequence is heads, and flipping over each coin of the
subsequence in place.  The game ends when all the coins are tails,
and play is normal--the player who is unable to move loses.

> I'm sorry I wasn't clear enough the first time. I hope this time
> there is no ambiguity in the meaning of the rules.

There never was any ambiguity, but people have to read carefully.

The way to evaluate a position is to (mentally) slide the coins
slightly out of line, so that they form a profile like the marks on a
ruler.  If we number the coins sequentially left to right, starting
at 1, this means that the odd coins are moved the least, the ones
numbered 2 mod 4 slightly more, the 4 mod 8 more, and so forth, with
the coins numbered 2^k mod 2^(k+1) moved to mental row k.  Thus you
should think of the position TTTTHTTHTHHTHTT

                             T T H T T H H T  (3 heads in row 0)
as if it were shifted to      T   T   H   T   (1 head in row 1)
                                T       T     (0 heads in row 2)
                                    H.        (1 head in row 3)

If you haven't got a fixed-pitch font for your newsreader you are out
of luck.  Draw it yourself.

You have lost if there are an even number of heads in each row.  If
not, you win by moving so there are.  In the example there are an odd
nubmer of heads in the units, twos, and fours rows, so the winning
move is to flip coins 7-11 to form TTTTHTHTHTTTHTT,

                                   T T H H H T H T (4 heads in row 0)
which we think of as                T   T   T   T  (0 heads in row 1)
                                      T       T    (0 heads in row 2)
                                          T.       (0 heads in row 3)

Or you could flip coins 1-13, if you prefer.  The parity of row k is
the 2^k bit of the nim-value of the position.  See _Winning Ways_, by
Berlekamp, Conway, and Guy, if you don't konw what this means.  In
fact, this game appears in _WW_ under the name "The ruler game".  But
I discovered this strategy not by looking it up, but by evaluating all
the positions with at most 15 coins (by machine) and analyzing the
results.  I understand from David Madore that his approach was similar.

Dan Hoey
Hoey@AIC.NRL.Navy.Mil