1
$\begingroup$

Consider the following game between two players A and B. Given are $2n$ numbers $a_1\dots a_{2n}$. The game consists of two phases:

1) Player A arranges the numbers in some suitable order.

2) In each turn, the player takes either the first or the last remaining number. Player B takes first. The player which larger sum of taken numbers wins.

Draws are excluded by assumption.

My conjecture is: regardless how player A arranges the numbers in the first phase, player B can always force a win.

For $n=1$ this is trivial. The reasoning for $n=2$ is as follows: Player A arranges the numbers to be $a_1\dots a_4$. By assumption (no draw possible) one of $a_1+a_3$ and $a_2+a_4$ is larger than the other. If $a_1+a_3>a_2+a_4$ player B takes $a_1$ and is guaranteed to be able to take $a_3$ in the next turn, thus B wins.

Is this game known under some particular name? Do you have any ideas how to prove the conjecture that B can force a win?

$\endgroup$
1
$\begingroup$

Hint-Do a few trials and for the winning solution, investigate the positions of B's numbers and you will notice a similiarity.

$\endgroup$
  • $\begingroup$ I did some trials, but do not notice a similarity besides 'both players play optimally'. Can you expand your answer? $\endgroup$ – daw Nov 5 '17 at 14:57
  • $\begingroup$ B either takes all the evens or all the odds. If B precalculates that say, the evens are greater, he can take all of them and win. He does this by taking the last number on his first go, then A has a choice of 2 odds. After A takes, B will take the even freed up by A, and so on. $\endgroup$ – Mike Nov 5 '17 at 15:07
  • $\begingroup$ The numbers to take are arbitrary, not just numbers $1$ to $2n$. Also A can arrange the numbers that B is not guaranteed to take an even number first. $\endgroup$ – daw Nov 5 '17 at 15:16
  • 1
    $\begingroup$ @daw I'll explain again, suppose that the game is with 8 numbers. If the numbers at a2,a4,a6,a8 are greater than those at a1,a3,a5,a7, B can take them by first taking a8. A can then take a1 or a7. A's move will have freed up a2 or a6, which B takes. Sorry I didn't use your ai notation earlier. $\endgroup$ – Mike Nov 5 '17 at 15:33
  • $\begingroup$ Thank you! I thought much too complicated. Doing something like recursion/induction does not lead to anything. $\endgroup$ – daw Nov 6 '17 at 7:03

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.