Mojtaba and Hooman are playing a game. Initially Mojtaba draws $2018$ vectors with zero sum. Then in each turn, starting with Mojtaba, the player takes a vector and puts it on the plane. After the first move, the players must put their vector next to the previous vector (the beginning of the vector must lie on the end of the previous vector). At last, there will be a closed polygon. If this polygon is not self-intersecting, Mojtaba wins. Otherwise Hooman. Who has the winning strategy? Proposed by Mahyar Sefidgaran, Jafar Namdar
Problem
Source: Iranian TST 2018, second exam day 1, problem 2
Tags: combinatorics, Iran, Iranian TST, game strategy, game, Game Theory
18.04.2018 14:10
I assumed that the directions of the vectors are determined by Mojtaba (if that's not the case, then Hooman can simply put a vector on top of the other one). The answer is that Mojtaba wins. The example consists of the vectors $(0,2017)$, called up vector, $1004$ piece of $(1003,-1)$, called right vectors and $1003$ piece of $(-1004,-1)$, called left vectors. Mojtaba puts the up vector first. Now, observe that the remaining vectors all go down, so if the polygon is self-intersecting, the intersection must lie on the up vector. This requires the sign of the sum of x-coordinates to swap. Case 1: Hooman puts the right vector next. In each of his moves, Mojtaba will put the right vector (as long as he can). Note that at any moment, the right vector will be used at least once more than the left vector, so the sum of x-coordinates is at least $1003k-1004(k-1)=1004-k\geq 0$, with $k$ being the number of used right vectors. See that the equality condition is to have used all the vectors, thus the intersection is the beginning of the up vector. Also see that when there are no right vectors left to put, then they both simply will use the left vectors, and as the total sum is zero, it can't go negative. Case 2: Hooman puts the left vector next. In each of his moves, Mojtaba will put the left vector (as long as he can). Similarly, the left vector will be used at least once more, thus the sum is at least $-1004k+1003(k-1)=-k-1003$ before they use all of the left vectors. After they used all the left vectors, as the total sum is zero, it can't go positive as they use the remaining right vectors. Thus, Mojtaba can assure that the polygon won't self-intersect.
22.07.2022 14:39
I wanted to point out a slightly simpler strategy than @above, but they are both quite simple regardless. Indeed, Mojtaba wins. Mojtaba takes $2016$ horizontal unit vectors from $(1,0)$ which we shall denote by $\textit{A}$ and $2$ other vectors $(-1008,1)$ and $(-1008,-1)$ which we shall the $\textit{B}$ vectors. Then, Mojtaba’s strategy is to first pick an $A$ vector at each step if no $B$ vector has been picked previously or there are no more $A$ vectors to be picked, then the sequence of vectors will either be $AA \cdots ABBA \cdots A$ where Mojtaba picks the second $B$ or $AA \cdots AABB$ where there are $2016$ $A$ vectors that are picked in the beginning and Mojtaba picks either of the two $B$ vectors in his last move. It is then easy to see that the process will result in a translation and reflection of the triangle with vertices $(0,0)$, $(2016,0)$, and $(1008,1)$. $\blacksquare$