Bologna Sandwich was worried about an upcoming test in Discrete Mathematics and was finding it hard to get to sleep. Bologna awoke early in the morning, aroused by devilish laughter, only to see an impish looking homunculus sitting at the bottom of the bed next to a seemingly infinite pile of chips. Hello, Bologna, it said, would you like to play a little game? This pile contains 43546758443209876 chips and the bottom chip represents your immortal soul. The rules are quite simple. The first player removes some chips, but not all of them. After that we take turns removing some chips.

The only rule now is that a player cannot remove more than the previous player removed in his last turn. The winner is the player who takes the last chip. If I win I get to keep your soul and if you win, you get an A in the test. Would you like to go first or second? This seemed a reasonable bet to Bologna.

Can you give Bologna a strategy for playing no matter how many chips there are? (What if there were just one more chip in the initial pile?)

What if the rule were that one is allowed to take up to twice the number of chips the previous player took?

(In reply to Is there any way... by Charlie)

Iain's strategy (if I understand) is to basically take the highest power of two chips that the pile is divisible by.  If you can't on the first turn, it is because the whole pile is a power of two and you can't take the whole pile in the first turn.  Therefore, if there is a power of two on your turn, you cannot win unless you can take the whole pile.

To shorten the playing time find the lowest power of two that is more than half of the original number.  For your first move, leave that number of chips.  This almost halves the game time.

Posted by Tristan on 2004-05-10 18:08:03