In this version of Nim, a move is to cross out any number of consecutive "sticks" in one row.

Here is a reply I posted to a similar question some years back.

[ Editor: the earlier posting, "Re: Vim anyone?", follows. ]

mikeg@amiganet.chi.il.us (Mike Glass) writes:

>Here's an old game which I believe I have figured the trick to winning each
>time, but want to make sure.  you have a pyramid of marks like this:

>                                  |
>                                | | |
>                              | | | | |
>                            | | | | | | |

>You may mark off how many ever you want as long as they are in a row
>and are together.  The last person to mark off the last mark loses.  I
>believe if you go first and do the move I am thinking off (won't post
>it for those who wish to figure for themselves) you will always win.

A winning strategy for simpler versions of this game has long been
known. I believe I first saw it in one of Martin Gardners Mathematical
Games books (where the game is called Nim). In the simplest version,
the player to take the last mark *wins* and there is no requirement
that the pieces are *together* (just that they are in the same row). I
will start with this, and then show how to modify it the other case.

The idea is to convert the number of marks in the rows to binary.
This yields in the example above the following numbers:

        001
        011
        101
        111

You then XOR (exclusive or) the numbers (yielding 000 in the example).
If the number is zero, then the next player loses (if the other player
plays perfectly). I will use the term "losing position" to mean any
position that results in a loss by the *next* player.

Proof:

By induction:

Base case: If there are no marks left, the "next" player has lost (the
preceding player has just removed the last mark).

Inductive case: If the XOR is 0, any number of marks removed from that
row will change at least on bit in that row, so the XOR cannot remain
0. What we then need to prove is that any non-zero position can be
changed to a zero position in one move.

We call the result of the XOR x. We look at the most significant 1-bit
of x. At least one of the row numbers must have that bit set, so we
select any such row, call that number r. We then make r' = r XOR x. r'
is less than r (because we required that r had the most significant
1-bit of x set). If we replace r by r' (which we can do by
subtraction), we now get a zero XOR (x') of the rows. This is seen
easily by x' = x XOR r XOR r' = x XOR r XOR (x XOR r) = 0.
                                                                []

This is how far Gardners book got, but I did a bit of further work
myself. We now first change the victory condition to be that the last
person to take a mark loses. The "obvious" solution that zero XOR is
now a winning position is wrong, as we cannot force a player to
convert a non-zero XOR position to a zero XOR position. It turns out
that for most of the game, a zero XOR position is still a losing
position! The only zero XOR positions that are winning positions
consist entirely of rows with only one mark. It is easy to see that
they are winning positions, so what we need to show is that they are
the only non-losing zero XOR positions. So we state the following
theorem: Any zero XOR position that has at least one row with two or
more marks is a losing position.

Proof:

A move either removes a row that contain only one mark, or removes any
number from a row that contains more than one mark.

In the case where a one-row is removed, we must have another row that
contains an odd number of marks. Removing one mark from this row will
make the position a zero XOR position, and will not change the number
of rows that contain at least two marks. So by induction we are back
in a losing position.

We note that if one row contains two or more marks in a zero XOR
position, at least one more row will do so. If we assume that at
least three rows do so, no two moves will remove the last such row, so
our general zero XOR preserving strategy will preserve a losing
position. If there are exactly two rows with more than one mark and
some marks are taken from one, we consider the two cases: more than
one mark was left, or at most one mark was left.

If at most one mark was left, we can reduce the other row to zero or
one mark, whichever will let the position consist of an odd number of
one-mark rows. This is obviously a losing position.

If at least two marks are left, we still have two rows with at least
two marks. Since our zero XOR preserving strategy will only take marks
from one row, we get a zero XOR position with at least one row of two
or more marks, which by our induction assumption is a losing position.

Thus we have a winning strategy also for the case where the last
person to take a mark loses.

Now we try to generalize to the case where you require marks to be
together. Note that we can reformulate the requirement to say that a
move splits a row into two rows, such that the total number of marks
is less than the number of marks in the initial row. Either (or both)
of these numbers can be zero.

We note that since we can do any move that we could do before, we can
still convert any non-zero XOR position into a zero XOR position in a
single move. But we must show that it is not possible to obtain a zero
XOR position from another in *one* move. In addition to this, we need
to find out which zero XOR positions are not losing positions, and
which non-zero XOR positions are.

We can in one move take out any row number and replace it by two row
numbers. If we want to retain the same XOR, then for any 1-bit in the
original number, exactly one of the new numbers must have that bit
set. If we ignore (subtract) the other bits in the new numbers, and
add the results, we get a sum that is equal to the original number.
Thus we cannot have a sum that is less than the original number.

In addition to the non-zero XOR positions that were losing positions
before (odd number of one-mark rows), we also have to consider the
possiblity of zero XOR positions that can yield these in one move (as
they are now winning), and non-zero XOR positions that can one of
those (as they are now losing) etc.

If we want to reach a position consisting entirely of one-mark rows,
we must start with a position that contain at most one row with more
than one mark. We can either delete that row, leave one mark or split
it into two one-mark rows. The latter has the same effect as deleting
it entirely, so we have no new possibilities.

Thus, a winning strategy is:

If there are only one-mark rows, remove any. If the resulting number
of rows is odd, you win, otherwise you lose.

If there is exactly one row with two or more marks, reduce this to
leave an odd number off one-mark rows. You win.

If there are more than one row with more than one mark, then find the
XOR (x) of the rows. If x is zero, you have lost, so make any move. If
x is non-zero, make a move that makes it zero. This can be done by
taking any row that has a number that shares the most significant bit
with x and replace it by the number obtained by XORing it with x. You
win.

Thus your claim that the first player would win in the game you

-- Torben AEgidius Mogensen <torbenm@diku.dk> (July 1994)

An excellent treatment of impartial two-player games of perfect
information (of which your game is one) is "Winning Ways" by Berlekamp,
Conway & Guy.  All such games can be analysed using Sprague-Grundy
theory, which is straightfoward for many "normal-play" games (if you
can't move you lose) but rather difficult for "misere play" games (if
you can't move you win).  I won't go into the details; read the book
yourself (it's entertaining and very readable).
                                       .
The game you describe is "Octal Game 0.7" which is the authors notation
for a game of heaps in which you can take any number of items from a
heap, and leave the remainder in 0, 1 or 2 heaps (see page 91).  The
analysis of your game (in the normal-play version) appears in the table
on p. 113, and in fact turns out to be exactly the same as ordinary nim,
in which you have to cross out sticks from one end. 

To see why it's the same, just note that you have all the options that
you would in a game of ordinary nim, and the other options just
duplicate nim-values that you could get by making ordinary nim moves.
For example, deleting the middle stick from a row of 5 is just the same
(in nim terms) as deleting all 5 sticks.
                    .
In the octal game 0.7 (normal-play), the nim-value of a row of k sticks
is k.  To find the nim-value of a position of several rows, nim-add the
nim-values of the individual heaps (to nim-add, represent the numbers in
binary and exclusive-or them).  If the nim-value is 0 then the player to
move loses; if it is not 0, then the player to move can win by finding
an option that reduces the nim-value to 0 (there will always be one).
                                                    * * * * * *
For example, the value of the triangle position is 1+2+3+4+5+6+7 = 0, so
there is no good move.

The misere version is "tame" (i.e. easy to analyse).  You play it just
like you would the normal version unless your move would leave an even
number of singleton heaps and no others.  Then leave an odd number
instead (see p. 393).


-- Gareth Rees <gdr11@cl.cam.ac.uk> (July 1994)

[ Editor: see also competition/games/nim.1357 for ordinary Nim. ]