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.”)



Share this post:

| More

Previous post:

Next post:



  • Paul

    Good post. I spent a couple days trying to come up with a proof by induction. (I realized Alice had the advantage for any even number of coins) Had I just observed who got which coins in a few sample games, I would have been much better off (I had to give in and come back for the solution).

    With an odd number of coins, Bob gets to choose between the evens and (remaining) odds on his first turn. As long as the absolute difference between the sum of the evens and the sum of the odds is greater than the coin Alice took, Bob has the advantage.

    In other words, Bob has the advantage if the following is true in the initial configuration of coins:

    abs(sum(odds) – max(first, last) – sum(evens)) > max(first, last)

    where first and last are the denominations of the first and last coins.

  • Cody F.

    Depending on the actual denomination of the coin Alice chooses first, it is likely that Bob has the advantage in a 51 coin game. This is because once Alice has chosen a coin, the problem is back to being a 50 coin problem with Bob picking first, giving him the same advantage that Alice had in that case.

  • Chuck D.

    The game should be subtitled “Heads I win tails you lose 25 times”. Alice merely has to look and determine which of her choices leaves Bob with two coins lesser and equal to hers. It could only be more unfair if someone kept pulling two coins from a jar and always giving Alice the first choice.

  • Faraz S.

    Yeah, I was also trying an induction on even numbers of coins. I’m wondering whether it’s still possible as an alternative proof. (No success so far, though!)

    A great problem!

  • Ibrahim

    Is that the maximum Alice can make? Or do we assume thats the maximum because Bob will also try to maximise hit coins, and Alice has to both get the most possible, and limit Bobs choices at the same time.

  • http://www.mindyourdecisions.com/blog/ Presh Talwalkar

    Good observations by Chuck and Cody–it’s really weird how the number of coins is so important.

    As for Ibrahim’s question, this is not the maximum Alice can make, but rather the minimum if Bob pursues the best strategy.

  • William

    As for maximizing, consider this:

    Say Alice counts the coins and determines that the odds are worth more. However, partway through the game, after collecting most of the large-value odd coins, Alice recounts and sees that now the even coins are worth more. She should then switch to collecting those.

    But, how often should she switch? Is it better to recount after each turn or is there a better long-term strategy? Also, is there anything that Bob can do to deter Alice from collecting even more?

  • http://None SauPa

    My Prof. set out this very e.g. for the class. I scoured the internet and presented the same solution.
    My prof. called the odds and evens solution as CHEAP. and said that an elegant solution requires higher math that my class can handle.

    So can a strategy be developed that does not depend on ODDS / EVENs logic?

  • http://dontlookhere.com house-zat

    I would be very interested in knowing another proof of the above result.

    Also does anyone know as to how to get an optimal strategy for this problem?

  • Adi

    I am a bit confused.
    If bob makes an arrangement:
    1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1.
    Where the number represents the denomination of the coin.
    If Alice is allowed to start first then Alice is always forced to pick a smaller denomination coin while Bob always picks up a 2 which will sum up to be greater than that of Alice.

  • http://www.mindyourdecisions.com/blog/ Presh Talwalkar

    AdiAdd up your array and uou’ll find out the odd terms and even terms have the same sum of 37, so Alice can always guarantee a tie. She will not be picking only 1′s because both the 25th and 26th coins are 1′s which changes the parity: it will mean Bob will have to pick the 1′s the rest of the game.





Previous post:

Next post:

Other posts you may enjoy reading:

This site is for recreational and educational purposes only (privacy policy)

Powered by WordPress