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?

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

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$ – theSongbird Oct 13 '17 at 7:27
  • $\begingroup$ There are many ways to prove it. Use whatever works for you. $\endgroup$ – Yuval Filmus Oct 13 '17 at 7:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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