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


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?

  • 1
    $\begingroup$ Where did you encounter this problem? Can you credit the source of the problem? Thank you. $\endgroup$
    – D.W.
    Oct 14, 2017 at 17:19

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

  • $\begingroup$ Ok, I got why it works. A formal proof using contradiction would be enough to proove it, you reckon? $\endgroup$ Oct 13, 2017 at 7:27
  • $\begingroup$ There are many ways to prove it. Use whatever works for you. $\endgroup$ Oct 13, 2017 at 7:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.