Maths Olympiad Prep

Library / /263 of 299

Combinatorics Difficulty 7.4 National Olympiad, round 2 Prove it Iran

Mojtaba and Hooman are playing a game. Initially Mojtaba draws 20182018 vectors with zero sum. Then starting with Mojtaba, each player takes a vector and puts it on the plane. After the first move, the players must put the starting point of their vector on the end of the vector that the previous person drew, until a closed polygon is established. If this polygon is not self-intersecting, Mojtaba is the winner and otherwise Hooman is the winner. Who has a winning strategy?

Solution

Mojtaba has a winning strategy.
Let him consider a large vector V\vec{V} to the left direction and 20172017 small vectors facing towards right. Let these vectors be V=(V,0)\vec{V} = (-V, 0), v1=(x1,y1)\vec{v}_1 = (x_1, y_1), v2=(x2,y2)\vec{v}_2 = (x_2, y_2), \dots, v2017=(x2017,y2017)\vec{v}_{2017} = (x_{2017}, y_{2017}). So that we have
x1++x2017=V, 1i2017:xi>0 x_1 + \dots + x_{2017} = V, \quad \forall\ 1 \le i \le 2017 : x_i > 0
and
y1++y2017=0. y_1 + \dots + y_{2017} = 0.
On his first move, Mojtaba chooses the large vector V\vec{V} and places it on the plane.
Figure 1
Now both players must select a vector from the remaining vectors, which all are from left to right. Therefore none of these small vectors intersect each other, and the only possible way to have a pair of vectors intersecting each other is to have a small vector ui\vec{u}_i that cuts V\vec{V} at some point other than the two ending points of V\vec{V}. Assume that ui=(xi,yi)\vec{u}_i = (x_i^*, y_i^*) is the first vector to intersect with V\vec{V} (u1=(x1,y1)\vec{u}_1 = (x_1^*, y_1^*), ..., u2017=(x2017,y2017)\vec{u}_{2017} = (x_{2017}^*, y_{2017}^*)) is a permutation of the vectors, sorted by the time they're chosen). There's two cases, we either have yj>0,j<iy_j^* > 0, \forall j < i and y1+y2++yi<0y_1^* + y_2^* + \cdots + y_i^* < 0, or yj<0,j<iy_j^* < 0, \forall j < i and y1+y2++yi>0y_1^* + y_2^* + \cdots + y_i^* > 0. So we can translate the problem as following.
There are 20172017 real numbers y1,,y2017y_1, \dots, y_{2017} with y1++y2017=0y_1 + \dots + y_{2017} = 0. Each player, starting from Hooman chooses a number yky_k and writes it on the plane. Assume that numbers are arranged by y1,y2,,y2017y_1^*, y_2^*, \dots, y_{2017}^*, in order of the time they're chosen. Without loss of generality assume that y10y_1^* \ge 0 (we will define yiy_i's so that there's no loss of generality, see the following). Mojtaba wins if for all i2017i \le 2017 we have
Si=y1++yi0. S_i = y_1^* + \cdots + y_i^* \ge 0.
Also add this assumption that Mojtaba drew the initial 20182018 vectors such that 12i+1,2j2017:y2i+1=y2j=1\forall 1 \le 2i + 1, 2j \le 2017 : y_{2i+1} = -y_{2j} = 1 except for 2i+1=13972i + 1 = 1397 where y1397=0|y_{1397}| = 0. Now the winning strategy is quite simple. In each move, Mojtaba only needs to choose a positive (or if y1<0y_1^* < 0, a negative) yiy_i^*, if such yiy_i^* exists. Otherwise, he chooses an arbitrary remaining number. Now we have
S2=y1+y21 S_2 = y_1^* + y_2^* \geq 1
We also always have Si0S_i \ge 0 unless all non-negative yiy_i^*'s are chosen, and Mojtaba is forced to choose from the remaining negative numbers. Now if there's an index i2017i \le 2017 such that Si<0S_i < 0, since S2017=0S_{2017} = 0, there must be an index j>ij > i such that yj>0y_j^* > 0. But this is impossible, because Si<0S_i < 0 means Mojtaba is out of positive numbers to choose from, so yjy_j^* cannot exist which is a contradiction. Thus, there's no such ii and the claim that Mojtaba has a winning strategy is proved. ■

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.