Optimizing greedy solution for choice game

Question

Consider the following game: Two players choose numbers from a sequence of integers with even number of elements. The two can only choose from either the front or the end of the sequence. The purpose is to pick a series of numbers that form a sum greater than the opponent's. The first player always starts and tries to beat the second player, which chooses his numbers randomly. Develop a strategy with which the first player always wins. By winning we consider that the first player's sum is greater or at least equal to the second player's sum.

My solution (greedy): At each step, P1 chooses the greater number between the front and the end of the sequence. At the end Sum(P1) >= Sum(P2).

Example:

S: 4 5 3 1
P1: 4
P2: 5 or 1
P1: if P2 picks 1, then P1 picks 5 || if P2 picks 5, then P1 picks 3
P2: picks either 3 or 1, depends on P1's choice
Sum(P1) (= 9 or 7) >= Sum(P2) (= 6 or 4)

Problem: For certain sequences, the above greedy approach does not compute a greater sum for P1. For S: 1 2 80 3, if P1 will choose 3 as it is greater than 1. If P2 then picks 80, the game is lost for P1.

My take on this situation: We scan S for it's greatest numbers and compare them to the greatest sum of numbers chosen up to them and create a strategy for P1 so that he chooses the greater number/ numbers. In the example above we find that 80 > 3 +1 (possible sum up to it), so P1 will first choose 1. This way P2 will have to pick from 5 and 3. After P2 chooses, P1 picks 80 and wins.

Thoughts on this?

Answer 1

The first player cannot always win – consider the case in which all numbers are the same. But we can always guarantee a draw. Here is the strategy – I'll let you figure out why it works.

Given the sequence $a_1,\ldots,a_{2n}$, calculate $a_{odd} = a_1 + a_3 + \cdots + a_{2n-1}$ and $a_{even} = a_2 + a_4 + \cdots + a_{2n}$. If $a_{odd} > a_{even}$, always pick odd indices. If $a_{even} > a_{odd}$, always pick even indices. Otherwise, the game is a draw.