Archive for June 17th, 2008

Conundrum: Nim, Part II

Tuesday, June 17th, 2008

You have defeated Iachimo at his own game, and he’s not happy.

“I usually go first,” he says icily. “Surely you will allow me a rematch, and allow me to go first this time.”

You know that, with his standard set up using piles of 1, 2, 3, 4, and 5, he can force a win by going first, so you decline. But he comes up with a surprising offer: you can increase the number of piles.

As before, the piles will start at 1 coin and will increase by 1 coin until the desired number of piles is reached. So if you decide to increase to six piles, the coin amounts must be 1, 2, 3, 4, 5, and 6. You’ve only got a limited number of coins available, so you may not exceed ten piles.

Iachimo will go first and you will take turns drawing coins from the piles. On your turn, you may remove as many coins as you like from any one pile. The winner is the one who takes the last coin and leaves his opponent without a move.

“Double or nothing,” he dares you, with a bit of desperation in his voice. You’re not sure what would happen if you decline. It doesn’t matter, though, since you see a clear path to victory, even allowing Iachimo to go first.

How many piles do you set up? What’s your strategy for winning?

UPDATE: Problem solved by Alex. See comments for solution.