Proof that you can win at least half the money.

Question

Suppose you play a game in which $n$ stacks of money each of different values, $a_1, ..., a_n$ are in a sequence on a table. You get to choose either the left-most or right-most stack, then your opponent can do the same, and so on, until all stacks are gone.

I need to prove that player 1 can always win at least half the money available when $n$ is even. I initially tried induction but the inductive step wasn't clear.

Suppose that you know the claim is true for $n=2k$ and consider a sequence of $2k+2$ stacks. Picking the maximum of the two end stacks will not always result in an optimal choice. If for instance the stacks are 1, 2, 100, 3 then as player 1 you might greedily choose 3 but then player 2 can choose 100. If you instead selected 1 then player 2 would be forced to select a sub-optimal stack and you get the grab the 100.

But I'm not sure how to prove this in general. Certainly if the stacks are $a_1, ..., a_{2k+2}$ and if $a_1$ is maximal then it's optimal to pick that, and likewise for $a_{2k+2}$. But there are also examples where $a_2$ is maximal and yet it's not optimal to pick $a_{2k+2}$. For instance 3, 4, 3, 1. The optimal selections go

Player 1: 3

Player 2: 4

Player 1: 3

Player 2: 1

Then player 1 has done better than trying to force player 2 to reveal the 4 stack.

Player 1: 1

Player 2: 3

Player 1: 4

Player 2: 3

One could theorize that if the max is $a_2$ or $a_{2k+1}$ and if that plus $\min\{a_1,a_{2k+2}\}$ is bigger than $\max \{a_1,a_{2k+2}\}+\min\{a_2,a_{2k+1}\}$ then you play the "defensive" strategy. But after playing it, there's no guarantee that player 2 will reveal the max on the next move. So I'm getting lost in the proof.

Answer 1

First player can ascertain to obtain $a_1+a_3+a_5+a_7+\cdots$ or $a_2+a_4+a_6+\cdots$, whatever they prefer.

Answer 2

I need to prove that player 1 can always win at least half the money available when n is even.

Expanding on Hagen van Eitzen's answer which is correct but doesn't offer much in the sense of explaination:

Given that n is even, we can dive the stack in two groups, {s1, s3, s5, ...} and {s2, s4, s6, ...}. The number of stacks in this group are equal (since n is even) and either the money is both groups is equal or one of the two groups contains more money than the other.

Either way, player one can choose to pick from group one (take stack 1) or group 2 (take stack n). After that, player two has no choice but to pick from the other group. Player one can than take from the preferred group again.

Worst-case scenario is when the money in group 1 equals that in group 2, and player one can take exactly half the money by sticking to either group 1 or 2. Otherwise, this strategy will give player 1 more than half the money.