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?

If Bologna goes first, he must take an even number. Since 43546758443209876 is divisible by 4, taking 2 to start would not work, since the imp could take 2, and continue until there were only two left and it was the imps turn to play, allowing him to win.

But since 43546758443209876 is not divisible by 8, taking 4 would work. If the imp continued to take 4, eventually there would be 4 left for Bolgna to take, and he would win. If at any point the imp took 3 or 1, Bologna would have an odd number and could go for the strategy of taking only 1. If the imp took 2, Bologna could continue to take 2 and eventually win, since the number he would be left with would not be divisible by 4.

This strategy works for any even number that is not a power of 2, by going first and taking the highest power of 2 that is not a factor of the number of chips in the pile.

If the number is a power of two, Bologna should go second. Since the number cannot be reduced to another power of two by taking less than half of it, and if the imp takes half or more Bologna wins instantly, any number that the imp takes will reduce the pile to either an odd number or a non-power of 2. Bologna can then win by using the strategy above for a non-power of 2.

This still leaves the puzzle of being allowed to take double the chips though.

 

Posted by Iain on 2004-05-10 12:46:25