Getting rich by counting: the coins in a row puzzle

Yes, getting rich is about saving and earning. But it is also about competition. Winning in the job, stock, and housing markets is about outsmarting opponents and thinking strategically. In such games, it is often important to make the right move before the action begins, as the next puzzle illustrates.

The puzzle

I came across an interesting puzzle in Peter Winkler’s Mathematical Puzzles called “Coins in a Row”

On a table is a row of fifty coins, of various denominations. Alice picks a coin from one of the ends and puts it in her pocket; then Bob chooses a coin from one of the (remaining) ends, and the alternation continues until Bob pockets the last coin.

Prove that Alice can play so as to guarantee as much money as Bob.

The implication of the game is mind-blowing. This is a seemingly fair game that is rigged for the first player. No matter how the second player arranges the coins, it is impossible for him to end up with more money.

Why is this the case?

Getting started

The puzzle is hard to approach because it is difficult to imagine all the distributions of fifty coins of various denominations. So let’s build up from a few observations.

Observation 1: Alice and Bob end up with the same number of coins

Since Alice and Bob alternate picking, they end up with 25 coins apiece. This is a rather trivial observation but it turns out to be useful to solving the puzzle.

Observation 2: If the coins were the same denomination, then Alice and Bob end up with the same amount of money

This directly follows from observation 1. It is easy to see that if all the coins were pennies, nickels, dimes, or quarters, then Alice and Bob would end up with equal valued sums.

This observation again is trivial, but it illustrates that Alice’s advantage comes from the precise arrangement of coins of various denominations.

Observation 3: By going first, Alice can affect which coins she picks

To see this, suppose the coins on the table are numbered 1 to 50 from left to right. The amazing part is that Alice by playing first jcan guarantee that she can pick all the odd-numbered coins 1, 3, 5, … 49, or she can all the even-numbered coins 2, 4, 6, …, 50. How is that possible?

To begin, consider what happens if Alice starts the game by picking coin 1. In this case, Bob is forced to choose among coins 2 and 50. Notice that Bob’s choices are both even-numbered coins. This means regardless of what Bob picks, he cannot grab an odd-numbered coin, and additionally he has to leave Alice with an odd-numbered coin. If Bob picks coin 2, then Alice can pick coin 3 (leaving 4 and 50 for Bob). If Bob picks coin 50, then Alice can pick 49 (leaving 2 and 48 for Bob). This logic can be extended, and consequently, Alice can collect all of the odd-numbered coins.

A similar argument demonstrates that Alice can guarantee she can pick all the even-numbered coins if she starts by picking coin 50.

Putting it all together: the solution

Now Alice’s strategy can be formulated. Before the game starts, Alice computes the sum of all of the odd-numbered coins and the even-numbered coins. One of the two sets has to at least be as big as the other (also an application of the pigeonhole principle).

Therefore, Alice can pick the set that gives her at least as much as Bob.

Bonus: what if the game has 51 coins?

If the game has 51 coins, how does that change the game?

(Hint: Winkler’s text says “However, if there are 51 coins instead of 50, it is usually Bob (the second to play) who will have the advantage, despite collecting fewer coins than Alice.”)