An even number of coins with known values lies in a row. Players alternately take one coin from either end and keep it. Show the first player can always guarantee at least half the total value, and say whether that strategy plays optimally.

An even number of coins with known values lies in a row. Players alternately take one coin from either end and keep it. Show the first player can always guarantee at least half the total value, and say whether that strategy plays optimally.

Approach: Number the positions and compare the total on odd positions with the total on even positions, then check which positions the opponent can reach after each of your moves.

The first player guarantees at least half by comparing the sum over odd numbered positions with the sum over even numbered positions and then taking only from whichever set is larger. Number the positions 1 to 2n. At the start both ends are an odd position and an even position. Whenever the first player takes an odd position from an end, the two exposed ends both become even positions, so the opponent is forced to hand back an odd end, and the mirror statement holds for the even set. So the parity strategy collects the entire odd sum or the entire even sum, whichever is larger, and that is at least half the total. It is a guarantee and is not designed to maximise the take. The true optimum comes from a dynamic programming recursion over intervals and runs in O(n^2).

Follow-up: Write the interval recursion for the optimal take and explain why the inner term is a minimum rather than a maximum?

Key concepts: parity of positions, guaranteed half, dynamic programming.