6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Can you do an example with four distinct numbers instead of 3,4,3,1 ? $\endgroup$ – WW1 Mar 28 at 4:25
6
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ This doesn't seem to cover all cases. The first seems to assume that player 2 always picks the left stack after player 1 picks left. The second seems to assume player 1 picks the right stand and player 2 picks right. Surely there are situations where player 1 optimizes with $a_1, a_2, a_3$ and player 2's optimal response is $a_6,a_5,a_4$, for instance. $\endgroup$ – Addem Mar 28 at 4:37
  • 4
    $\begingroup$ @Addem: Player $1$ can guarantee to get the odd-numbered stacks, just not necessarily in order. First take $a_1$. Then the end stacks both have even indices ($2$ and $2n$), and no matter which one Player $2$ takes, the remaining layout will have a stack with an odd index at one end and a stack with an even index at the other. Player $1$ takes the stack with an odd index, and so on. $\endgroup$ – Brian M. Scott Mar 28 at 5:18
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

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.