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.
How? With 50 coins, label the coins from 1 to 50. Add up the values of all the odd-numbered coins. Separately, add up the values of the even-numbered coins. If one of the sums is greater than the other, the first player wins by picking the appropriately numbered coins.
Indeed, it’s always possible to do so. Suppose, for example, that the even-numbered coins have a larger sum than the odd-numbered coins. The first player starts by picking the last (50th) coin. The two end coins now have odd-numbered labels. The second player has to pick an odd-numbered coin. This leaves an even-numbered coin for the first player to choose.
The game can be played with any number of coins. With an odd number of coins, however, the situation is more complicated. For example, if you had just three coins—a penny, a nickel, and a penny—the first player would lose. But, if you had a nickel, a penny, and a nickel, the first player would win.
“If there are 51 coins instead of 50, it is usually [the second player] who will have the advantage, despite collecting fewer coins than [the first player],” Winkler writes in his book Mathematical Puzzles: A Connoisseur’s Collection (A K Peters, 2004).
“It seems paradoxical that the parity of the number of coins has such a huge effect on the outcome of this game, in which all of the action takes place at the ends,” he adds.
So, even seemingly simple games can have unexpected complications. Indeed, “no matter how simple something is,” Winkler says, “there’s room for it to be too hard to do.”
In the even-numbered case of the coin game, for instance, although there’s a strategy by which the first player can at least earn a draw, it’s not clear whether it’s the best strategy for winning. Or even the “right” strategy to use.
It’s certainly possible to analyze a given game, with a certain number of coins of various denominations, to find the appropriate coin-choosing strategy to follow in that game. But no one has yet worked out an optimal strategy that works for any number of coins.
Moreover, it’s easy to come up with variants of the coin game that present new problems. What if the coins were in a ring? What if you wanted to maximize the amount by which you beat your opponent?
There’s always more to investigate—presenting all sorts of new challenges.
