Coins in a Line


I got this problem from Rustan Leino, who got it from Rajeev Joshi, who got it from Jay Misra.

I solved it and wrote up my solution.


Consider a game that you play against an opponent. In front of you are an even number of coins of possibly different denominations. The coins are arranged in a line. You and your opponent take turns selecting coins. Each player takes one coin per turn and must take it from an end of the line, that is, the current leftmost coin or the current rightmost coin. When all coins have been removed, add the value of the coins collected by each player. It is possible that you and your opponent end up with the same value (for example, if all coins have the same denomination). Develop a strategy where you take the first turn and where your final value is at least that of your opponent (that is, don't let your opponent end up with coins worth more than your coins).

Solution     Reveal