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

The strategy

On every turn, do the following. Consider the coins to form two alternating sequences. One such sequence contains the leftmost coin and one contains the rightmost coin. Choose the coin that belongs to the alternating sequence with the greater total value. (If the two sequences have the same total value, choose arbitrarily.)

Why it works

Call the score the final value of your coins minus the final value of your opponents' coins. The aim is to get a non-negative score.

We now prove that, for all even $n$, following the strategy above when there are $n$ coins left achieves a score of at least $|L - R|,$ where $L$ is the total value of the alternating sequence that includes the leftmost coin and $R$ is the total value of the alternating sequence that includes the rightmost coin.

We prove it by induction on $n.$ Clearly, it's true for $n=2,$ since the strategy leads to choosing the highest remaining coin. We now prove it holds for $n=N$ assuming it holds for $n=N-2.$

Suppose you choose the leftmost coin. Call its value $a.$ This was part of the sequence that added up to $L,$ so what remains of that sequence sums to $L-a.$ Then, your opponent will choose one of the remaining coins on the end; call it $b.$ That coin was part of the sequence that added up to $R,$ so what remains of that sequence sums to $R - b.$ Furthermore, the remaining sequences are interleaved, so we're left with $N-2$ coins in two interleaving sequences, one summing to $L-a$ and one summing to $R-b.$

Applying the inductive hypothesis, we see that your score for the remainder of the game will be at least $|(L-a)-(R-b)|.$ Since $|x| \geq x$ for all $x$, this is at least $(L-a)-(R-b).$ So your total score for the game will be at least this plus the $a-b$ earned in the first two turns. That is, it will be at least $a-b+(L-a)-(R-b) = L-R.$ By assumption, you chose the leftmost coin while following the strategy, so it must be that $L \geq R.$ Thus, $L-R = |L-R|$ so your score winds up being at least $|L-R|.$

The other case to consider is if you choose the rightmost coin. By a symmetrical argument, your score winds up being at least $R-L$ which is $|L - R|.$

This completes the induction, so the statement is proved. The absolute value $|L-R|$ is always non-negative, so following the strategy must always yield a non-negative score. In other words, you'll wind up with at least as much total value as your opponent, which is the aim. $\Box$