Sunday, May 08, 2005

Mathematical puzzle of the day: "Coins In A Row"
Suppose you have 50 coins -- a mixture of pennies, nickels, dimes, and quarters -- arranged in a line on a tabletop. You choose a coin from one of the ends and put it in your pocket. Your opponent then chooses a coin from one of the ends of the line of remaining coins. You and your opponent take turns removing a coin in this manner until your opponent takes the last one. The player with the larger amount of money wins.

Peter Winkler of Dartmouth College describes it as "the simplest game in the world." There are just two players. There's no chance involved. There's no hidden information; everyone sees what's going on. There are at most two options per move.

In this coin game, it's possible to prove that, starting with an even number of coins of any denomination, the first player can always guarantee getting at least as much as the other player.
If you want to check your solution, click here.