a game -- splitting piles of stones

Given an initial pile of n stones.

2 players alternate turns.

At each turn, the player must choose one of the remaining piles of
stones and split it into 2 or 3 piles (not necessarily of equal size).
Since stones are not breakable, any pile of size 1 can't be split, and
hence survives intact for the rest of the game. If there are no piles
that can be split, the player whose turn it is loses.

For which values of n is the game a win for player 1?

For those values of n, specify an optimal strategy.

The game has a very simple solution, but I'll let people play.

I made up the above game by generalizing a game I found in a text
designed for a math enrichment course for liberal arts students. The
game in the textbook was the same except the player is required to
split a pile into exactly 2 piles. The requirement to split a pile
into exactly 2 piles makes the game trivial, so I revised it in order
to make it harder.

In my revised game, I expected that it might need some programming to
identify the optimal strategies. In fact, that was part of my goal --
to create a game which was not immediately obvious and such that
solving the game would make for a fun programming problem.

As it turns out, I couldn't solve it myself when I first tried it. I
couldn't even come up with a nice algorithm so that I could write a
program to solve it.

Having no algorithm, I was forced to abandon the idea of a computer
solution and so I struggled with it theoretically until, all of
sudden, a key idea hit me. Based on that insight, the solution was
immediate, and the form of the solution is actually quite nice.

It still bothers me that I wasn't able to formalize the search for a
solution in terms of a simple algorithm, but I guess it's just another
example of where human insight is superior to the power of a computer.

quasi
.

Relevant Pages

  • Re: Game with coins
    ... In ordinary nim these are the same game and the first player ... the middle pile cannot be touched, and these are two distinct games. ... Take the game, so far the only move which player 1 can make ... coins from the first pile, then the second player is not forced to take coins away from the pile with 5 coins, but can now also take coins from the pile with 2 coins. ...
    (sci.math)
  • What the game Nim was really meant to have been; finding a Nim with draw possibility
    ... back to the creation origins of the game and I suspect the game may have ... Historical Nim: I am guessing that historically Nim ... Say tribe A comes laden with lots of gifts of objects and dumps them ... into a pile and tribe B has its pile of objects. ...
    (sci.math)
  • What the game Nim was really meant to have been; finding a Nim with draw possibility
    ... back to the creation origins of the game and I suspect the game may have ... Historical Nim: I am guessing that historically Nim ... Say tribe A comes laden with lots of gifts of objects and dumps them ... into a pile and tribe B has its pile of objects. ...
    (sci.logic)
  • Re: Game with coins
    ... In ordinary nim these are the same game and the first player ... the middle pile cannot be touched, and these are two distinct games. ... Take the game, so far the only move which player 1 can make ... The game is basically a sequence of 2-pile Nim games, ...
    (sci.math)
  • Re: Tuesday Top 5: Online Multiplayer Games
    ... Steam(ing pile of poo) came out. ... With Steamyou first needed to activate the game online every time you play. ...
    (uk.games.video.misc)