Let $n>1$ be an integer. Suppose we are given $2n$ points in the plane such that no three of them are collinear. The points are to be labelled $A_1, A_2, \dots , A_{2n}$ in some order. We then consider the $2n$ angles $\angle A_1A_2A_3, \angle A_2A_3A_4, \dots , \angle A_{2n-2}A_{2n-1}A_{2n}, \angle A_{2n-1}A_{2n}A_1, \angle A_{2n}A_1A_2$. We measure each angle in the way that gives the smallest positive value (i.e. between $0^{\circ}$ and $180^{\circ}$). Prove that there exists an ordering of the given points such that the resulting $2n$ angles can be separated into two groups with the sum of one group of angles equal to the sum of the other group.
Problem
Source: IMO Shortlist 2019 C6
Tags: IMO Shortlist, combinatorics, IMO Shortlist 2019, angles, combinatorial geometry
23.09.2020 02:41
Windmills, anyone? Divide the plane into two halves, each containing $n$ points. Then label one half with odd labels and the other with even labels. Take line $\ell$ to be $A_1 A_{2n}$. After rotation of the line across all the points (pivoting on each of the points and rotating to the next, i.e. $A_1 A_2$ pivots on $A_2$ to rotate to $A_2 A_3$), the directed rotated angle of the line is a multiple of $180^{\circ}$. But $\ell$ couldn't have rotated more than $180^{\circ}$ as it cannot be parallel to the half-plane line (otherwise it would coincide with the half-plane line or $\ell$ would be contained in one half, contradiction), so it's zero. Divide the angles into sets of positive and negative angles. We're done. Remark: I found the idea of this problem easier than C1. Oops.
23.09.2020 02:42
23.09.2020 09:44
Solution suggested by one of the Thailand TST group members. Orient the coordinate axis so that no two points have the same $y$-coordinate. Label points $P_1,P_2,\hdots,P_{2n}$ by the decreasing order of $y$-coordinate. We claim that the explicit choice $$P_1\to P_{n+1}\to P_2\to P_{n+2}\to\hdots\to P_n\to P_{2n}\to P_1$$(where $A_{2i-1} = P_i$ and $A_{2i}=P_{n+i}$) works. To see why, consider the windmill, which is a ray. Initially, the windmill is pointed along the ray $\overrightarrow{A_1A_2}$. At the $i$-th minute, the windmill is rotated by the angle $\measuredangle A_iA_{i+1}A_{i+2}$ (indices modulo $2n$). Observe that after the $2i$-th minute, the windmill is pointing at the direction $\overrightarrow{A_{2i+2}A_{2i+1}}$, and after the $2i-1$-th minute, the windmill is pointing at the direction $\overrightarrow{A_{2i}A_{2i+1}}$. However, notice that the points $A_{2i-1}$ and $A_{2i+1}$ are both "higher" than $A_{2i}$, and the points $A_{2i}$ and $A_{2i+2}$ are both "lower" than $A_{2i+1}$. Combining these facts, we see that the windmill's span is always restricted by the upper half-plane determined by the $x$-axis. After the $2n$-th minute, the windmill has come back to the original position but it never makes a full turn. Thus, by grouping angles with makes the windmill sweep counterclockwise together, we obtain the desired partition.
24.09.2020 17:51
Straight induction solution sketch: Redefine angle notation so that it's signed: the sign of $\angle ABC$ is positive if and only if the rotation bringing ray $BA$ to ray $BC$ that is $< 180^\circ$ is counterclockwise. The problem thus asks for a labelling such that $\angle A_1A_2A_3+\angle A_4A_5A_6...+\angle A_{2n-1}A_{2n}A_1+\angle A_{2n}A_1A_2=0$. It is not hard (by just verifying a few cases) to show the LEMMA: $\angle CBA = \angle DBA - \angle DBC$. Proceed with induction, on the statement that for ANY segment $AB$ of the convex hull, it is possible to assign $A = P_1$ and $B=P_2$ so the statement holds. The base cases, $3$ and $4$, are just casework depending on the convex hull of the four points. Now, the inductive step: Let $H$ be the convex hull of the points. Case 1: $H$ has $\geq 4$ points. Given edge $AB$, consider any other edge of the convex hull, not including $A$ or $B$; label the endpoints $A_1,A_2,A_3,A_4$ so that on the convex hull, the clockwise order of the points is $A_1, A_4, A_2, A_3$ (i.e. $A_1A_2$ and $A_3A_4$ intersect) and the edges are $A_1A_4$ and $A_2A_3$. Remove $A_2$ and $A_3$ and use the inductive hypothesis on edge $A_1A_4$ (which is obviously still an edge of the new convex hull), giving us $\angle A_1A_4A_5+ \angle A_4A_5A_6+...+\angle A_{2n}A_1A_4 = 0$ (where $A_1,A_4$ correspond to the original $A_1$ and $A_4$). Then we can check that the labelling $A_1,A_2,...A_{2n}$ works (where $A_2,A_3$ are the original $A_2,A_3$), using the lemma. Case 2: $H$ has $3$ points. Consider edge $A_2A_3$ of $H$ and let $A_1$ be the other vertex of $H$, where the clockwise ordering is $A_1,A_2,A_3$. Sweep $A_1A_2$ clockwise with pivot $A_1$ and let $A_4$ be the first point reached. Then, remove $A_2A_3$ and use the inductive hypothesis on $A_1A_4$ to get a labelling with $\angle A_1A_4A_5+ \angle A_4A_5A_6+...+\angle A_{2n}A_1A_4 = 0$ (where $A_1,A_4$ correspond to the original $A_1$ and $A_4$). Similar to above we can then use the lemma to show that $A_1,A_2,...A_{2n}$ is a successful labelling, where $A_2,A_3$ are the original $A_2,A_3$. This completes the inductive step and the proof (details are omitted, but they are not hard).
21.05.2021 20:54
Solution. So we construct a $2n$ regular gon ,and in the left hand side we let the $A_i$ vertices for $i$-odd, and similarly in the RHS we let the $A_j$ vertices for $j$-even. We have that $\overline {A_iA_{i+1}}$ is paralel to $\overline{A_{i+2}A_{i+3}}$ Let us have to groups $G_1$ and $G_2$ such that $G_1$ contains the angles $\angle A_{i-1}A_iA_{i+1}$ so that $i$-is odd, similarly $G_2$ set of angles $\angle A_{j-1}A_jA_{j+1}$ so that $j$-is even. and we can easily see that the sum of the angles in these two groups is the same! (Using the parallel lines) [asy][asy] /* Geogebra to Asymptote conversion, documentation at artofproblemsolving.com/Wiki go to User:Azjps/geogebra */ import graph; size(20cm); real labelscalefactor = 0.5; /* changes label-to-point distance */ pen dps = linewidth(0.7) + fontsize(10); defaultpen(dps); /* default pen style */ pen dotstyle = black; /* point style */ real xmin = -10.6, xmax = 10.44, ymin = -6.23, ymax = 7.73; /* image dimensions */ pen dtsfsf = rgb(0.8274509803921568,0.1843137254901961,0.1843137254901961); pen wrwrwr = rgb(0.3803921568627451,0.3803921568627451,0.3803921568627451); /* draw figures */ draw((xmin, -80.33333333333334*xmin-67.85666666666667)--(xmax, -80.33333333333334*xmax-67.85666666666667), linewidth(2) + dtsfsf); /* line */ draw((-3.14,4.77)--(1.3311743845756592,4.825657772422104), linewidth(2) + wrwrwr); draw((-4.34,2.95)--(1.3311743845756592,4.825657772422104), linewidth(2) + wrwrwr); draw((-4.34,2.95)--(2.576106730934757,3.0360926149079024), linewidth(2) + wrwrwr); draw((2.576106730934757,3.0360926149079024)--(-4.84,1.05), linewidth(2) + wrwrwr); draw((-4.84,1.05)--(3.123247374763299,1.149127560681701), linewidth(2) + wrwrwr); draw((3.123247374763299,1.149127560681701)--(-4.68,-0.57), linewidth(2) + wrwrwr); draw((-4.68,-0.57)--(3.003622654501636,-0.4743532449647098), linewidth(2) + wrwrwr); draw((1.4403814770184207,-2.7739786538130486)--(-3.14,4.77), linewidth(2) + wrwrwr); draw((-3.06,-2.83)--(1.4403814770184207,-2.7739786538130486), linewidth(2) + wrwrwr); /* dots and labels */ dot((-3.14,4.77),dotstyle); label("$A_1$", (-3.06,4.97), NE * labelscalefactor); dot((-4.34,2.95),dotstyle); label("$A_3$", (-4.26,3.15), NE * labelscalefactor); dot((-4.84,1.05),dotstyle); label("$A_5$", (-4.76,1.25), NE * labelscalefactor); dot((-4.68,-0.57),dotstyle); label("$A_7$", (-4.6,-0.37), NE * labelscalefactor); dot((-3.06,-2.83),dotstyle); label("$A_{2n-1}$", (-2.98,-2.63), NE * labelscalefactor); dot((1.3311743845756592,4.825657772422104),dotstyle); label("$A_2$", (1.42,5.03), NE * labelscalefactor); dot((2.576106730934757,3.0360926149079024),dotstyle); label("$A_4$", (2.66,3.23), NE * labelscalefactor); dot((3.123247374763299,1.149127560681701),dotstyle); label("$A_6$", (3.2,1.35), NE * labelscalefactor); dot((3.003622654501636,-0.4743532449647098),dotstyle); label("$A_8$", (3.08,-0.27), NE * labelscalefactor); dot((1.4403814770184207,-2.7739786538130486),dotstyle); label("$A_{2n}$", (1.52,-2.57), NE * labelscalefactor); clip((xmin,ymin)--(xmin,ymax)--(xmax,ymax)--(xmax,ymin)--cycle); /* end of picture */ [/asy][/asy]
29.03.2022 05:29
By discrete continuity, there is a line $\ell$ that divides the plane into two half-planes, both of them containing exactly $n$ points. Let $A_1$ be the leftmost point on the plane. Assume WLOG that $A_1$ is below $\ell$. Let $A_2$ be the leftmost point that is above $\ell$. Let $A_3$ be the point below $\ell$ such that the angle $\angle A_1A_2A_3$ does not contain any point below $\ell$. Let $A_4$ be the point above $\ell$ such that the angle $\angle A_2A_3A_4$ does not contain any point above $\ell$. Similarly, define $A_5,A_6,...A_{2n}$ in a way that all odd indices are below $\ell$ in increasing order and all even indices are above $\ell$ in increasing order. Let $\ell_1=A_1A_2, \ell_2=A_2A_3,...,\ell_{2n-1}=A_{2n-1}A_{2n}, \ell_{2n}=A_{2n}A_1, \alpha_i=180º- \angle A_iA_{i+1}A_{i+2}$ for odd $i$ and $\beta=180º- \angle A_iA_{i+1}A_{i+2}$ for even $i$. Moreover, let $\angle \ell, \ell_i$ denote the smallest angle between $\ell,\ell_i$. Clearly, $\alpha_i= \angle \ell_{2i-1}, \ell +\angle \ell_2i, \ell$ and $\beta_i= \angle \ell_{2i-2}, \ell + \ell_{2i-1}, \ell$ (indices $\pmod{2n}$). Hence, $\sum_{i=1}^n \alpha_i= \sum_{i=1}^n \beta_i $ $\implies \sum_{2 \nmid i} \angle A_iA_{i+1}A_{i+2}= \sum_{2|i} \angle A_iA_{i+1}A_{i+2}$, as desired.
21.07.2022 17:10
We may divide plane by line $a$ into two half-planes with $n$ given points in each one. We claim that it's suffice to label point from one half-plane with odd labels, and other with even labels. Let $A_{2n}A_1=\ell ,$ so $$R_{A_{2n}}^{\measuredangle A_{2n-1}A_{2n}A_1}...\circ R_{A_2}^{\measuredangle A_1A_2A_3}\circ R_{A_1}^{\measuredangle A_{2n}A_1A_2} (\ell )=\ell,$$in particular sum $S$ of rotation angles is $\pi n$ for $n\in \mathbb{Z}$. But we easily see that $\ell$ was never parallel to $a$ while rotating, since it couldn't lie in one half-plane (or coincide with $\ell$), thus $S=0$ and it's suffice to consider sum of positive angles, and of other.
23.12.2023 17:59
Call the angles $\alpha_1=\angle A_{2n}A_1A_2$ and analogously for $\alpha_2,\dots,\alpha_{2n}$. Divide the plane into two regions, each with $n$ points. Oddly index the points on one side and evenly index the other. If we start a line at $A_{2n}A_1$, then pivot about $A_1$ to $A_1A_2$, we turn $\pm \alpha_1$ counterclockwise. The next pivot if we pivot to $A_2A_3$ we turn $\pm \alpha_2$ counterclockwise. If at any point the net amount we turned is more than $\pi$ or less than $-\pi$ then that means the poles of our line have switched sides. That is, the side of our line that used to be odd is now even. Clearly, this cannot happen. Thus, having pivoted to $A_{2n-1}A_{2n}$ and ultimately back to $A_{2n}A_1$, our net turn is $0$. Thus, \[\pm \alpha_1\pm \alpha_2\pm \alpha_3\pm \dots \pm \alpha_{2n}=0\]as desired.
04.01.2024 07:27
lets do this boys: same as #3 Orient the path so that it looks like $A_1\to A_{\sigma(2)}\to \dots \to A_{\sigma(2n)}\to A_1$. We classify angles $\angle A_{k-1}A_kA_{k+1}$ as left or right turns in the obvious way. (Motivation: Basically if we only consider the angle formed by "right turns" then it clearly makes sense to group the inverted left turns.) Now the point is that there is some path where the sum of angles of left turns and sum of angles of right turns are the same. Consider monovariant $M=\sum {\text{left turn angles}}-\sum {\text{right turn angles}}$. We need to first show $M$ is a multiple of $2\pi$. Fortunately this is pretty easy; it suffices to show that the sum of all "right turn" angles is a multiple of $2\pi$, which is basically where we use the fact that there are an even number of points: do some crazy polygon things. (It's a bit more complicated than that, actually, you have to subtract $\pi$ from each angle, but eh.) Now as the monovariant for paths \[A_1\to A_{\sigma(2)}\to \dots \to A_{\sigma(2n)}\to A_1\]\[A_1\to A_{\sigma(2n)}\to \dots \to A_{\sigma(2)}\to A_1\]are negatives of each other we just need to show that swapping $A_k$ and $A_{k+1}$ changes the monovariant by at most $2\pi$. This is actually surprisingly easy. There are four angles that are modified. The easiest way for me to visualize this is by orienting $A_kA_{k+1}$ to point directly upwards. Then $\angle A_kA_{k+1}A_{k+2}$ switches from a left to a right turn or vice versa. The same holds for $\angle A_{k-1}A_kA_{k+1}$. We can actually prove that the change of the angles $\angle A_{k-2}A_{k-1}A_k$ and $\angle A_{k-1}A_kA_{k+1}$ is at most $\pi$. This is good enough. To prove it, notice that the change of the angle $\angle A_{k-1}A_kA_{k+1}$ is $\pm \pi\mp \angle A_kA_{k-1}A_{k+1}$. The change of the angle $\angle A_{k-2}A_{k-1}A_k$ can actually be upwards of $2\pi$. Essentially, there are two cases: If $\angle A_{k-2}A_{k-1}A_k$ and $\angle A_{k-2}A_{k-1}A_{k+1}$ are left and right turns or vice versa we obtain something like \[(\pm 2\pi\mp \angle A_kA_{k-1}A_{k+1})+(\mp \pi\pm \angle A_kA_{k-1}A_{k+1})=\pm \pi\]which is fine. If $\angle A_{k-2}A_{k-1}A_k$ and $\angle A_{k-2}A_{k-1}A_{k+1}$ are both left or right turns we obtain something like just $\pi$ which is fine. Yay(ups)!
06.02.2024 10:18
Nice but tricky problem in that the construction is hard to find; after that, the problem is immediate from windmill processes. It is well-known that there exists a line $\ell$ dividing the plane into two regions, each containing $n$ of the points. Impose a coordinate plane where the $x$-axis is $\ell$. Choose an arbitrary side of $\ell$, call the point with greatest $x$-coordinate $A_1$, and then label the points left-wards as $A_3$, $A_5$, and so on. Do the same thing on the other side of $\ell$, except with even indices. I contend that this labeling works. Now place an ant at $A_{2n}$, so that it is directed along the vector $\overrightarrow{A_{2n}A_1}$, and move it in that direction until it reaches $A_1$. Repeat this step along the vector $\overrightarrow{A_1A_2}$, and so on, until the ant reaches $A_{2n}$ again, and then redirect it along the vector $\overrightarrow{A_{2n}A_1}$. Okay, so what significance does this ant have? Modulo $2\pi$, the overall delta in the angular direction of the ant is the alternating sum of the angles $A_{i-1}A_iA_{i+1}$, which is $0$ radians. Thus we can group the $A_i$ by the parity of their index, and we are done.
24.08.2024 20:17
Let $\ell$ be a line that splits the points into two sets $\mathcal{X}$ and $\mathcal{Y}$. Choose a direction for $\ell$ and let $\vec{v}$ be a vector in that direction. Then, for $X\in \mathcal{X}$ and $Y\in \mathcal{Y}$, define $0< f(X, Y) < 180$ as the angle between $\vec{XY}$ and $\vec{v}$. Let $A_1,A_3,\dots, A_{2n-1}$ be the elements of $\mathcal{X}$ and $A_2,A_4,\dots,A_{2n}$ be the elements of $\mathcal{Y}$. Then, with indices taken mod $2n$, we have \[0 = \sum_{k=1}^{2n} f(A_k, A_{k+1}) - f(A_{k-1}, A_k) = \sum_{k=1}^{2n} \pm \angle A_{k-1}A_kA_{k+1}.\]