6
$\begingroup$

2n random numbers are laid in a row. We take turns to take a number. Each time, one can choose from the number on the tail or the head of the sequence/row. The one with the bigger summation wins the game. If I go first, can I always win (or tie)?

My approach:

Let's start with a base case of n = 1. In this case we can see both the numbers and guarantee a win (or tie in case both numbers are the same).

n=2: Let's say the numbers are 4, 1, 9, 10 and I pick 10 first between 4 and 10. Now the sequence is 4,1,9 and my opponent chooses 9 between 4 and 9. Now its my turn and I choose 4 between 4 and 1. Thus I can win.

Wondering if my approach is correct and if there is a more general solution for 2n numbers in this case

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ If the numbers are $\{4,1,19,10\}$, then choosing 10 is a loss. $\endgroup$
    – Daniel Mathias
    Commented Dec 17, 2023 at 19:48
  • 2
    $\begingroup$ What is your approach? You didn't seem to describe it in the post. $\endgroup$
    – Brady Gilg
    Commented Dec 18, 2023 at 6:28
  • $\begingroup$ I know the question has an already accepted answer but it should be noted this class of puzzles falls under Nim. $\endgroup$
    – wLui155
    Commented Dec 18, 2023 at 20:20

1 Answer 1

Reset to default
13
$\begingroup$

And the answer is...

yes, you will always win (or tie) against your opponent!

Why?

Compute the sum of the numbers placed in an odd position, and the sum of the numbers placed in an even position. If the odd sum is the biggest, start with the head of the row. Else, start with the tail.

Now:

Just make the same choices as your opponent. If he chooses the number at the head of the row, also pick the number at the head of the row. What you're doing is basically forcing your opponent to pick either all the numbers placed in an odd position or in an even position, according to your very first choice. Your first choice made him pick the smallest of the two sums, so you win! (or tie if both sums are equal)
Edit: As pointed out by Bass, having both sums equal does not mean you couldn't use another strategy to win (and not only tie) the game. This strategy guarantees to at least tie, but it is not optimal in every single case.

Improve this answer
$\endgroup$
1
  • 7
    $\begingroup$ The final sentence about tie games isn't exactly true: for example, if the game starts at "1 1 2 1 1 2", then the sums are equal, but the starting player still wins. I think this has to do with the starting player getting to swap their choice after each pair of moves. $\endgroup$
    – Bass
    Commented Dec 17, 2023 at 22:41

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