Newsgroups: sci.math
From: hoey@pooh.tec.army.mil (Dan Hoey)
Date: 1995/12/03
Subject: Re: Putnam spoilers -- Bean Problem

Brian David Rothbach <rothbach> writes:

> You're right, reducing the 3 bean pile to 2 beans wins.  The simple
> stategy is just don't reduce any 4 bean piles to 3 beans....
> Most complicated is if you take 1 bean from the four bean piles....
> Of course, I miscalculated this last case on my test.

This problem is completely uncomplicated if you apply Sprague-Grundy
theory, turning each pile of beans into a nim-heap:

  2-piles can move only to 0, so they act like nim-heaps of size 1;
  3-piles move to 2-piles (nim 1) or to 0, so they act like
    nim-heaps of size 2;
  4-piles can't move to any 0-heap, so they act like 0-heaps;
  5-piles move only to a 0-heap, so they act like 1-heaps; and
  n-piles, n>5 act like n-2-piles, or (n mod 2)-heaps.

The winning move from any position is to move so that there are an
even number of 2-heaps (3-piles) and an even number of 1-heaps
(2 or 5,7,9,... piles).  This is possible unless you already are in
such a position, in which case you have lost.

I'm surprised they didn't at least pose the game in its misere
variant, where some analysis of the special role of 3-piles seems to
be necessary.  I think then the strategy is to play the normal game as
long as there are at least two piles greater than 2, and thereafter to
move to positions with an odd number of 2-piles (and no others).

Dan
Hoey@AIC.NRL.Navy.MIl