Coins in a Row
9 Dec 2008
Puzzle

30 coins of arbitrary denominations are laid out in a row. Simran and Tavleen alternately pick one of the two coins at the ends of the row so as to pick up as much money as possible. If Simran makes the first move, could Tavleen ever collect more money than Simran, if Simran makes the optimal choices?

Source

From Mathematical Puzzles: A Connoisseur's Collection (163 pages, 2003) by Peter Winkler. Solving this puzzle for even 4 coins requires the right insight.

Solution

When the total number of coins is even, the first player could pick all coins in odd-numbered positions or all coins in even-numbered positions, whichever set is larger in value.

Followup

An Optimal Algorithm for Calculating the Profit in the Coins in a Row Game by Tomasz Idziaszek has algorithms for identifying the total payoff of the two players if both play optimally.

"Grabbing the Gold" by Deborah Seacrest and Tyler Seacrest, Discrete Mathematics, Vol 312, Issue 10, pages 1804-1806, May 2012.