Place 10 piles of 10 $1 bills in a row.

competition/games/nim Added material

Problem

Place 10 piles of 10 $1 bills in a row.  A valid move is to reduce
the last i>0 piles by the same amount j>0 for some i and j; a pile
reduced to nothing is considered to have been removed.  The loser
is the player who picks up the last dollar, and they must forfeit
half of what they picked up to the winner.

1)  Who is the winner in Waldo Nim, the first or the second player?

2)  How much more money than the loser can the winner obtain with best
    play on both parties?

Show solution

For the particular game described we only need to consider positions for
which the following condition holds for each pile:

        (number of bills in pile k) + k >= (number of piles) + 1

A GOOD position is defined as one in which this condition holds,
with equality applying only to one pile P, and all piles following P
having the same number of bills as P.
( So the initial position is GOOD, the special pile being the first. )
I now claim that if I leave you a GOOD position, and you make any move,
I can move back to a GOOD position.

Suppose there are n piles and the special pile is numbered (n-p+1)
(so that the last p piles each contain p bills).
(1) You take p bills from p or more piles; 
  (a) If p = n, you have just taken the last bill and lost.
  (b) Otherwise I reduce pile (n-p) (which is now the last) to 1 bill.
(2) You take p bills from r(<p) piles;
    I take r bills from (p-r) piles.
(3) You take q(<p) bills from p or more piles;
    I take (p-q) bills from q piles.
(4) You take q(<p) bills from r(<p) piles;
  (a) q+r>p; I take (p-q) bills from (q+r-p) piles
  (b) q+r<=p; I take (p-q) bills from (q+r) piles

Verifying that each of the resulting positions is GOOD is tedious
but straightforward.  It is left as an exercise for the reader.

    -- RobH

Additional material

An inexpensive paperback covers this and much more:

The Mathematics of Games, by John D. Beasley, Oxford U Press

Nice book.

-- Oren C. Webster <owebster@cris.com>