The question states:

Alice and Barbara play a game with a pack of $2n$ cards. On each of which is written a positive integer. The pack is laid out in a row, with the numbers facing upwards. Alice starts, and the girls take turns to remove one card from either end of the row, until Barbara picks up the final card. Each girl’s score is the sum of the numbers on her chosen cards at the end of the game. Prove that Alice can always obtain a score at least as great as Barbara’s.

My solution uses the idea that if we label the cards: $a_1,a_2 \cdots a_{2n} $

We can show that Alice can force Barbara to either pick up all the evens, or all the odds.

It then follows naturally that either the sum of the two sequences are equal or one is greater than the other.

What are some other solutions to this problem that use elementary methods? Describing the motivation for a solution would also be highly appreciated.

  • 2
    $\begingroup$ At each turn Alice can choose whether to force Barbara onto evens or onto odds (so can switch strategies if this is advantageous - so this potentially improves the outcome for Alice in practical play). Barbara always has a choice of two cards with the same parity. I don't think there is another simple strategy which works. There are sequences where Barbara can force Alice to stay on the same parity to get the best outcome, but if all the numbers on all the cards are the same there is no forcing (and no problem with achieving a tie either). $\endgroup$ – Mark Bennet May 17 '18 at 8:49

If you try to proceed by induction, you will find that your answer simplifies to the one you have given.

n=2. Alice chooses the higher card.

n=4. If A chooses $a_1$, the best strategy for B is to choose $\max\{a_2,a_4\}$. Now A gets $\max\{ a_3 , \min\{a_2,a_4\}\}$. Similarly if A chooses $a_4$, the best strategy for B is to choose $\max\{a_1,a_3\}$. Now A gets $\max\{ a_2 , \min\{a_1,a_3\}\}$. So A's total is the greatest of $a_1 +a_3$, $a_1 + \min\{a_2,a_4\}$, $a_4 +a_2$, $a_4, \min\{a_3,a_1\}$. You'll notice that A can choose between the odds and the evens, which means her total will be greater than B's if she chooses the better of these two strategies. Once you notice this, you can try n=6 and generalize.


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.