Problem (by amkach):
Consider the two player game that begins with an even
length fixed random sequence of positive integers. Each
player, in turn, removes either the first or last of the
remaining integers, ending when all the integers have been
removed. A player's score is the sum of the integers that
they removed; the winner is the player with the higher
score (with a tie if equal scores). Show that Player One
has a non-losing strategy, i.e., can always force a tie or
a win.
Hint: Start with shorter sequences
sequence (a b)
strategy: take the bigger one.
sequence (a b c d)
after taking a, the best the opponent can do is to take the
bigger of b and d. So when will the benefit of taking a
(instead of d) be greater than the loss of revealing b?
Strategy: compare a - b < d - c => take a (instead of d)
Result: suppose a-b >= d-c (by symmetry). If c is the
biggest of the remaining three, then first player gets
the two biggest numbers and wins. So let's suppose it
isn't and the second player gets the biggest and the
smallest of the remaining three. Let those be b > c > d,
so that the score will be a+c for the first player and
b+d for the second, so that a + c > b + d
But that's the same as the inequality we started with.
