5
$\begingroup$

A couple of weeks ago, I was idly reading some of the problems of the All Soviet Union Math Competitions, when I came across a fascinating problem from the 1992 edition, specifically problem 22 (which I've modified slightly to make more timely):

$2022$ arbitrary vectors are given in the plane. Alice and Bob take turns picking unpicked vectors, with Alice going first. Once all $2022$ vectors have been picked, the resultant vector for each player is calculated. The winner is whoever's resultant vector has the greater magnitude (or the game is a draw if both vectors have the same magnitude). Can Alice always avoid losing from the beginning, no matter Bob's strategy or the coordinates of the vectors?

My first thought was that Alice can always avoid losing by sequentially picking the remaining vector that gives the greatest running magnitude of the resultant vector, but that fails on (for example) the set of vectors composed of $(2,0)$ and $2021$ $(-1,0)$'s. Then my next thought was just to sequentially pick the remaining vector with the greatest magnitude, but that fails on the same set of vectors as above. Then I thought something linear algebra-related might work, but this was supposed to be a contest for high-schoolers, so that would be inappropriate as a solution even if one were to exist. Nothing else has come to me, and I'm burning my brain out trying to come up with new strategies. Any help anyone could give in finding a strategy would be greatly appreciated.

$\endgroup$
2
  • 1
    $\begingroup$ I do not know the solution of the problem, but I think changing $1992$ to $2022$ might make the problem differ by a lot. After all, it’s possible that the problem uses a property that the number $1992$ has but $2022$ does not, e.g. divisible by $4$. $\endgroup$
    – VTand
    Feb 6, 2022 at 7:11
  • $\begingroup$ Fair enough. In that case, an interesting question might be for which numbers of vectors Alice can guarantee that she can avoid losing for any set of vectors and coordinates of the vectors. $\endgroup$ Feb 6, 2022 at 7:13

1 Answer 1

5
$\begingroup$

Suppose there are $2n$ vectors.

Alice can avoid losing by using the following strategy . . .

Let $S$ be the sum of all $2n$ vectors.

On Alice's $i$-th turn, let Alice choose the vector, $a_i$ say, among the yet unchosen vectors such that the dot product $a_i\cdot S$ is largest, and let $b_i$ denote the vector chosen by Bob on his $i$-th turn.

Let $A=a_1+\cdots +a_n$ and let $B=b_1+\cdots +b_n$.

By choice of $a_i$, we have $a_i\cdot S\ge b_i\cdot S$.

It follows that $A\cdot S\ge B\cdot S$, hence $$ |A|^2-|B|^2 = A\cdot A-B\cdot B = (A-B)\cdot (A+B) = (A-B)\cdot S \ge 0 $$

$\endgroup$

You must log in to answer this question.

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