A Bean Game

When I was in England one summer, my friend Ossie Manners and I would invent and play silly little "bean games." In each of these games there are beans which players take turns removing. The player to remove the last bean wins/loses. One of these games turns out to be pretty interesting; this is the subject of this page.

The game itself is very simple. You start with one or more lines of beans. On a players turn he may either remove an entire line of beans or remove a single bean, breaking a line into two lines (unless it was at the end of a line). The player to remove the last bean loses.

For example, say we start with a single line of 3 beans. The legal moves are to remove all the beans (and immediately lose!), to remove an end bean (leaving a line of 2 beans) or remove the center bean (leaving two lines of 1 bean each). It's not hard to see that the first player to move loses.

So the main question is: given a game who wins? I have a few theoretical results and lots of computational results on this question.

Begin with the theory. Four things:

  1. Adding two 1-piles does not affect the winner.
  2. 3-piles may be changed to 1-piles without affecting the winner.
  3. Adding two 2-piles does not affect the winner, so long as there is already at least one 2-pile.
  4. Adding two n-piles does not affect the winner, so long as there are already sufficiently many n-piles.
I've proved items 1-3 (they're pretty easy). So far 4 is just an observation based on data.

Now some computational results. There are two classes of games I've done computations on. The first of these is the game with one pile of n beans, for which I've computed the winner up to n=75. The results are sort of cool: the winner alternates except at n=4,15,18 for which player A wins twice in a row. So starting with the game with a single bean, the winners are:

BABAABABABABABAABAABABABABABABABABABABA...

The second class of games I've computed results for are what I call "binary games." They have at most one n-pile for each n. Given an integer n we can form a binary game by writing n in binary and creating an i-pile if the ith digit is a 1 (call the ones place the 1st digit, not the 0th digit). I've computed the winner of the binary games from n=0 to a little less than 2^15. They make the following really cool pictures:



Black pixels are B-wins, grey pixels are A-wins and red pixels are games which haven't been computed yet. The top left pixel is game n=0. Moving right one pixel corresponds to incrementing n by one (and you just wrap around the edge of the picture).