# Solution to 20 Coins

###### By Joshua C. Teitelbaum

This is a variation of the “21 Flags” immunity challenge played on the sixth episode of the fifth season of the CBS reality television show Survivor. See, e.g., Avinash K. Dixit & Barry J. Nalebuff, The Art of the Strategy: A Game Theorist’s Guide to Success in Business and Life, 44–49 (2008).

Bob is sure to win the Flowing Hair Dollar, which must be chosen last, if he plays the correct strategy. To win the Flowing Hair Dollar, Bob must ensure that he has the last turn of the game. We can find Bob’s path to sure victory by backwards induction.

• To have the last turn of the game, Bob must face 3 or fewer coins at his last turn.
• To ensure this, Bob must leave 4 coins on the table at his previous turn.
• To ensure this, Bob must leave 8 coins on the table at his previous turn.
• To ensure this, Bob must leave 12 coins on the table at his previous turn.
• To ensure this, Bob must leave 16 coins on the table at his previous turn.

It follows that Bob can put himself on the path to sure victory by playing the following strategy: At each of his turns, Bob should (1) choose 1 coin if Alex chooses 3 coins, (2) choose 2 coins if Alex chooses 2 coins, and (3) choose 3 coins if Alex chooses 1 coin.