IMO 2019 Shortlisted Problems

Let $\ell$ be a line separating the points into two groups ($L$ and $R$) with $n$ points in each. Label the points $A_1,A_2,\dots ,A_{2n}$ so that $L=\{A_1,A_3,\dots ,A_{2n-1}\}$. We claim that this labelling works. Take a line $s=A_{2n}{A}_1$. (a) Rotate $s$ around $A_1$ until it passes through $A_2$; the rotation is performed in a direction such that $s$ is never parallel to $\ell$. (b) Then rotate the new $s$ around $A_2$ until it passes through $A_3$ in a similar manner. (c) Perform $2n-2$ more such steps, after which $s$ returns to its initial position. The total (directed) rotation angle $\Theta$ of $s$ is clearly a multiple of $180^{\circ }$. On the other hand, $s$ was never parallel to $\ell$, which is possible only if $\Theta =0$. Now it remains to partition all the $2n$ angles into those where $s$ is rotated anticlockwise, and the others.

---

Alternative solution.

When tracing a cyclic path through the $A_i$ in order, with straight line segments between consecutive points, let ${\theta }_i$ be the exterior angle at $A_i$, with a sign convention that it is positive if the path turns left and negative if the path turns right. Then ${\sum }_{i=1}^{2n}{\theta }_i=360k^{\circ }$ for some integer $k$. Let ${\varphi }_i=\angle A_{i-1}{A}_i{A}_{i+1}$ (indices $\mathrm{mod}2n$), defined as in the problem; thus ${\varphi }_i=180^{\circ }-|{\theta }_i|$. Let $L$ be the set of $i$ for which the path turns left at $A_i$ and let $R$ be the set for which it turns right. Then $S={\sum }_{i\in L}{\varphi }_i-{\sum }_{i\in R}{\varphi }_i=(180(|L|-|R|)-360k{)}^{\circ }$, which is a multiple of $360^{\circ }$ since the number of points is even. We will show that the points can be labelled such that $S=0$, in which case $L$ and $R$ satisfy the required condition of the problem. Note that the value of $S$ is defined for a slightly larger class of configurations: it is OK for two points to coincide, as long as they are not consecutive, and OK for three points to be collinear, as long as $A_i,A_{i+1}$ and $A_{i+2}$ do not appear on a line in that order. In what follows it will be convenient, although not strictly necessary, to consider such configurations. Consider how $S$ changes if a single one of the $A_i$ is moved along some straight-line path (not passing through any $A_j$ and not lying on any line $A_j{A}_k$, but possibly crossing such lines). Because $S$ is a multiple of $360^{\circ }$, and the angles change continuously, $S$ can only change when a point moves between $R$ and $L$. Furthermore, if ${\varphi }_j=0$ when $A_j$ moves between $R$ and $L$, $S$ is unchanged; it only changes if ${\varphi }_j=180^{\circ }$ when $A_j$ moves between those sets. For any starting choice of points, we will now construct a new configuration, with labels such that $S=0$, that can be perturbed into the original one without any ${\varphi }_i$ passing through $180^{\circ }$, so that $S=0$ for the original configuration with those labels as well. Take some line such that there are $n$ points on each side of that line. The new configuration has $n$ copies of a single point on each side of the line, and a path that alternates between sides of the line; all angles are $0$, so this configuration has $S=0$. Perturbing the points into their original positions, while keeping each point on its side of the line, no angle ${\varphi }_i$ can pass through $180^{\circ }$, because no straight line can go from one side of the line to the other and back. So the perturbation process leaves $S=0$.

---

Alternative solution.

First, let $\ell$ be a line in the plane such that there are $n$ points on one side and the other $n$ points on the other side. For convenience, assume $\ell$ is horizontal (otherwise, we can rotate the plane). Then we can use the terms "above", "below", "left" and "right" in the usual way. We denote the $n$ points above the line in an arbitrary order as $P_1,P_2,\dots ,P_n$, and the $n$ points below the line as $Q_1,Q_2,\dots ,Q_n$. If we connect $P_i$ and $Q_j$ with a line segment, the line segment will intersect with the line $\ell$. Denote the intersection as $I_{ij}$. If $P_i$ is connected to $Q_j$ and $Q_k$, where $j<k$, then $I_{ij}$ and $I_{ik}$ are two different points, because $P_i,Q_j$ and $Q_k$ are not collinear. Now we define a "sign" for each angle $\angle Q_j{P}_i{Q}_k$. Assume $j<k$. We specify that the sign is positive for the following two cases: - if $i$ is odd and $I_{ij}$ is to the left of $I_{ik}$, - if $i$ is even and $I_{ij}$ is to the right of $I_{ik}$. Otherwise the sign of the angle is negative. If $j>k$, then the sign of $\angle Q_j{P}_i{Q}_k$ is taken to be the same as for $\angle Q_k{P}_i{Q}_j$. Similarly, we can define the sign of $\angle P_j{Q}_i{P}_k$ with $j<k$ (or equivalently $\angle P_k{Q}_i{P}_j$). For example, it is positive when $i$ is odd and $I_{ji}$ is to the left of $I_{ki}$. Henceforth, whenever we use the notation $\angle Q_j{P}_i{Q}_k$ or $\angle P_j{Q}_i{P}_k$ for a numerical quantity, it is understood to denote either the (geometric) measure of the angle or the negative of this measure, depending on the sign as specified above. We now have the following important fact for signed angle measures: $$\angle Q_{i_1}{P}_k{Q}_{i_3}=\angle Q_{i_1}{P}_k{Q}_{i_2}+\angle Q_{i_2}{P}_k{Q}_{i_3}\text{\hspace{1em}(1)}$$ for all points $P_k,Q_{i_1},Q_{i_2}$ and $Q_{i_3}$ with $i_1<i_2<i_3$. The following figure shows a "natural" arrangement of the points. Equation (1) still holds for any other arrangement, as can be easily verified.



Similarly, we have $$\angle P_{i_1}{Q}_k{P}_{i_3}=\angle P_{i_1}{Q}_k{P}_{i_2}+\angle P_{i_2}{Q}_k{P}_{i_3}\text{\hspace{1em}(2)}$$ for all points $Q_k,P_{i_1},P_{i_2}$ and $P_{i_3}$, with $i_1<i_2<i_3$. We are now ready to specify the desired ordering $A_1,\dots ,A_{2n}$ of the points: - if $i⩽n$ is odd, put $A_i=P_i$ and $A_{2n+1-i}=Q_i$; - if $i⩽n$ is even, put $A_i=Q_i$ and $A_{2n+1-i}=P_i$. For example, for $n=3$ this ordering is $P_1,Q_2,P_3,Q_3,P_2,Q_1$. This sequence alternates between $P$'s and $Q$'s, so the above conventions specify a sign for each of the angles $A_{i-1}{A}_i{A}_{i+1}$. We claim that the sum of these $2n$ signed angles equals $0$. If we can show this, it would complete the proof. We prove the claim by induction. For brevity, we use the notation $\angle P_i$ to denote whichever of the $2n$ angles has its vertex at $P_i$, and $\angle Q_i$ similarly. First let $n=2$. If the four points can be arranged to form a convex quadrilateral, then the four line segments $P_1{Q}_1,P_1{Q}_2,P_2{Q}_1$ and $P_2{Q}_2$ constitute a self-intersecting quadrilateral. We use several figures to illustrate the possible cases. The following figure is one possible arrangement of the points.



Then $\angle P_1$ and $\angle Q_1$ are positive, $\angle P_2$ and $\angle Q_2$ are negative, and we have $$|\angle P_1|+|\angle Q_1|=|\angle P_2|+|\angle Q_2|.$$ With signed measures, we have $$\angle P_1+\angle Q_1+\angle P_2+\angle Q_2=0.\text{\hspace{1em}(3)}$$ If we switch the labels of $P_1$ and $P_2$, we have the following picture:



Switching labels $P_1$ and $P_2$ has the effect of flipping the sign of all four angles (as well as swapping the magnitudes on the relabelled points); that is, the new values of ($\angle P_1,\angle P_2,\angle Q_1,\angle Q_2$) equal the old values of ($-\angle P_2,-\angle P_1,-\angle Q_1,-\angle Q_2$). Consequently, equation (3) still holds. Similarly, when switching the labels of $Q_1$ and $Q_2$, or both the $P$'s and the $Q$'s, equation (3) still holds. The remaining subcase of $n=2$ is that one point lies inside the triangle formed by the other three. We have the following picture.



We have $$|\angle P_1|+|\angle Q_1|+|\angle Q_2|=|\angle P_2|.$$ and equation (3) holds. Again, switching the labels for $P$'s or the $Q$'s will not affect the validity of equation (3). Also, if the point lying inside the triangle of the other three is one of the $Q$'s rather than the $P$'s, the result still holds, since our sign convention is preserved when we relabel $Q$'s as $P$'s and vice-versa and reflect across $\ell$. We have completed the proof of the claim for $n=2$. Assume the claim holds for $n=k$, and we wish to prove it for $n=k+1$. Suppose we are given our $2(k+1)$ points. First ignore $P_{k+1}$ and $Q_{k+1}$, and form $2k$ angles from $P_1,\dots ,P_k$, $Q_1,\dots ,Q_k$ as in the $n=k$ case. By the induction hypothesis we have $$\sum _{i=1}^k(\angle P_i+\angle Q_i)=0.$$ When we add in the two points $P_{k+1}$ and $Q_{k+1}$, this changes our angles as follows: - the angle at $P_k$ changes from $\angle Q_{k-1}{P}_k{Q}_k$ to $\angle Q_{k-1}{P}_k{Q}_{k+1}$; - the angle at $Q_k$ changes from $\angle P_{k-1}{Q}_k{P}_k$ to $\angle P_{k-1}{Q}_k{P}_{k+1}$; - two new angles $\angle Q_k{P}_{k+1}{Q}_{k+1}$ and $\angle P_k{Q}_{k+1}{P}_{k+1}$ are added. We need to prove the changes have no impact on the total sum. In other words, we need to prove $$\left(\angle Q_{k-1}{P}_k{Q}_{k+1}-\angle Q_{k-1}{P}_k{Q}_k\right)+\left(\angle P_{k-1}{Q}_k{P}_{k+1}-\angle P_{k-1}{Q}_k{P}_k\right)+(\angle P_{k+1}+\angle Q_{k+1})=0.\text{\hspace{1em}(4)}$$ In fact, from equations (1) and (2), we have $$\angle Q_{k-1}{P}_k{Q}_{k+1}-\angle Q_{k-1}{P}_k{Q}_k=\angle Q_k{P}_k{Q}_{k+1}$$ and $$\angle P_{k-1}{Q}_k{P}_{k+1}-\angle P_{k-1}{Q}_k{P}_k=\angle P_k{Q}_k{P}_{k+1}.$$ Therefore, the left hand side of equation (4) becomes $\angle Q_k{P}_k{Q}_{k+1}+\angle P_k{Q}_k{P}_{k+1}+\angle Q_k{P}_{k+1}{Q}_{k+1}+\angle P_k{Q}_{k+1}{P}_{k+1}$, which equals $0$, simply by applying the $n=2$ case of the claim. This completes the induction.

---

Alternative solution.

We shall think instead of the problem as asking us to assign a weight $\pm 1$ to each angle, such that the weighted sum of all the angles is zero. Given an ordering $A_1,\dots ,A_{2n}$ of the points, we shall assign weights according to the following recipe: walk in order from point to point, and assign the left turns $+1$ and the right turns $-1$. This is the same weighting as in Solution 3, and as in that solution, the weighted sum is a multiple of $360^{\circ }$. We now aim to show the following:

Lemma. Transposing any two consecutive points in the ordering changes the weighted sum by $\pm 360^{\circ }$ or $0$.

Knowing that, we can conclude quickly: if the ordering $A_1,\dots ,A_{2n}$ has weighted angle sum $360k^{\circ }$, then the ordering $A_{2n},\dots ,A_1$ has weighted angle sum $-360k^{\circ }$ (since the angles are the same, but left turns and right turns are exchanged). We can reverse the ordering of $A_1,\dots ,A_{2n}$ by a sequence of transpositions of consecutive points, and in doing so the weighted angle sum must become zero somewhere along the way.

We now prove that lemma:

Proof. Transposing two points amounts to taking a section $A_k{A}_{k+1}{A}_{k+2}{A}_{k+3}$ as depicted, reversing the central line segment $A_{k+1}{A}_{k+2}$, and replacing its two neighbours with the dotted lines.



Figure 1: Transposing two consecutive vertices: before (left) and afterwards (right)

In each triangle, we alter the sum by $\pm 180^{\circ }$. Indeed, using (anticlockwise) directed angles modulo $360^{\circ }$, we either add or subtract all three angles of each triangle. Hence both triangles together alter the sum by $\pm 180\pm 180^{\circ }$, which is $\pm 360^{\circ }$ or $0$. $\square$