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

Reset to default
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$
5
  • $\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, 2017 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$
    – user445435
    Nov 5, 2017 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, 2017 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$
    – user445435
    Nov 5, 2017 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, 2017 at 7:03

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .