4
$\begingroup$

For a positive integer n, a row of n cards is laid out, each showing a random positive integer. A legal move is to remove either the leftmost or rightmost card. Two players, A and B, take turns, with A going first. On each turn, A must take two cards if at least two remain, or one card if only one remains, while B takes exactly one card per turn. When all the cards have been taken, each player adds up the numbers on their cards, and A wins if the total value of the cards collected by A is at least two-thirds of the sum of all card values. The question asks for which values of n player A can guarantee a win regardless of how the numbers are arranged.

Could anyone provide a better way to approach this problem?

Thank you in advance.

$\endgroup$
7
  • 1
    $\begingroup$ What's a random positive integer? If one card has value more than a third of the sum, $A$ needs to get it, so the strategy is heavily dependant on the values. $\endgroup$ Commented Oct 18 at 5:15
  • 2
    $\begingroup$ I think its more dependent on the inequality or relations between the values on the cards such that $\frac{2}{3}$ of the sum can be guaranteed $\endgroup$ Commented Oct 18 at 5:19
  • $\begingroup$ Aside from defining a random positive integer, more context is needed. Is there a reason to believe this has a solution? That is, is there a reason to think the existence of a winning strategy is only a function of $n$ and not of the values? $\endgroup$ Commented Oct 18 at 5:32
  • $\begingroup$ Well, this question is taken from an official mathematics olympiad combinatorics practice set, and all information in the problem has been provided. $\endgroup$ Commented Oct 18 at 5:38
  • 1
    $\begingroup$ To see that $5$ fails, suppose we had two big cards, each over a third of the sum. Put them second and third. Then nothing $A$ does can prevent $B$ from getting one of them. Perhaps that can be extended to larger $n$. $\endgroup$ Commented Oct 18 at 6:29

1 Answer 1

Reset to default
3
$\begingroup$

A partial answer: Player $A$ can guarantee a win for $n$ a multiple a 3.

Index the cards from $0$ to $n-1$ and consider the residues of each index modulo 3. The initial layout looks like $$0 \quad 1 \quad 2 \quad 0 \quad 1 \quad 2 \quad \dots \quad 0 \quad 1 \quad 2$$

Let $S_i$ be the sum of the random numbers on all cards with residue $i$, where $i = 0, 1, 2$. By the pigeonhole principle, at least one $S_i$ (say, $S_0$) must be $\leq \frac13 S$.

Then, Player $A$ simply needs to pick all the cards with residue 1 and 2, as that would force Player $B$ to pick all cards with residue 0. Since $S_1 + S_2 = S - S_0 \geq \frac23 S$, Player $A$ wins.

For the case where $n$ is not a multiple of 3, one might be able to use the above logic to construct an assignment of random numbers that do not guarantee a win for Player $A$.

$\endgroup$
4
  • 2
    $\begingroup$ Nice construction (+1). To finish, take 2 big cards, each over a third, placed second and third. Neither player can choose the first card, so they both work from the end. Now considering the number of cards $\pmod 3$ you can see that $A$ fails in the other two cases $\endgroup$ Commented Oct 18 at 7:12
  • $\begingroup$ I don't see how A can force a pick all the cards with residue 1 and 2. Suppose that 3 of ths cards are in a row. No matter what A does, B has the option of picking one of them. $\endgroup$ Commented Oct 18 at 15:14
  • $\begingroup$ @btilly As his first move, $A$ can pick the last two cards, which have residues 1 and 2. Then $B$ has the option between the 0th and $(n-3)$-indexed card, both of which have residue 0. After $B$ chooses either card, say the 0th indexed card, $A$ can take the 1st and 2nd-indexed card. Rinse and repeat. $\endgroup$ Commented Oct 18 at 15:53
  • $\begingroup$ @asdia Oh. Residues of the index, not the value! Very clever. $\endgroup$ Commented Oct 18 at 16:51

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.