If Alice and Bob sequentially select from arbitrary vectors, can Alice guarantee a not-lesser resultant

contest-mathgame theoryoptimizationvectors

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.

Best Answer

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 $$

Related Question