Newsgroups: rec.puzzles
From: Hoey@AIC.NRL.Navy.Mil (Dan Hoey)
Date: 1997/04/12
Subject: Re: Puzzle : Striking off sticks.

ta...@singnet.com.sg (ghola) writes:

>      1  Group 1 (1 stick)
>     11  Group 2 (2 sticks)
>    111  Group 3 (3 sticks)
>   1111  Group 4 (4 sticks)
>  11111  Group 5 (5 sticks)
> 111111  Group 6 (6 sticks)
> How to play:
> - 2 players take turn to strike off any number of sticks from any group.
> - To strike off 2 or more sticks in a group, the sticks must be side
>   by side....
> - If striking off one/some of the sticks from in between a group,
>   then the remaining sticks on the right and on the left are now
>   consider 2 distinct groups....
> Objective:
> - In order to win, you must leave one last stick for your opponent
>   to strike off.
> Question:
> - Is there a sure win or higher winning chance strategy?

This game (also known as ".777...") appeared on rec.puzzles in 1992,
but is not in the latest version of the archives I've seen (1993).
David Grabiner showed that this a tame game, played as if it were the
same position in Nim (aka ".333...").  That is, it is never necessary
to use the ability to split the remnant of a group, and your opponent
will not gain by doing so.  (Though in misere play, the disjunctive
compound of this game with a non-tame game may not admit this
simplification).  But you were asking...

> - If so, how do you do it with you starting first?

As in Nim, play to make the nim-sum of the group sizes zero, EXCEPT
(since this is misere) when you are leaving no group with more than
one stick, when you make the nim-sum one.  You calculate the nim-sum
(sometimes called the "exclusive-or" or the "GF(2) sum") by writing
the numbers in binary notation and adding them together without
"carrying" from one bit position to another.  (It is not hard to learn
to calculate nim-sums in your head.  Impress your friends!  Confound
your opponents!)

In the given position, the EXCEPTion is not yet in effect, so you must
change the nim-sum from 7 to zero.  You do this by nim-adding 7 to the
value of some group.  Change

group 4 to (4 nimsum 7)=3   (x111 or 1x11)   since (1 nimsum 2)=3,
group 5 to (5 nimsum 7)=2  (xxx11 or 1x111)  since (1 nimsum 3)=2, or
group 6 to (6 nimsum 7)=1 (xxxxx1 or 11x111) since (2 nimsum 3)=1.

You can find out why this strategy works in any of hundreds of books
and papers on Nim, but you will learn best from Berlekamp, Conway, and
Guy's book _Winning Ways_.

Dan Hoey
Hoey@AIC.NRL.Navy.Mil