IMO 2011 · Problem 2

Let \(S\) be a finite set of at least two points in the plane. Assume that no three points of \(S\) are collinear. A windmill is a process that starts with a line \(\ell\) going through a single point \(P\in S\). The line rotates clockwise about the pivot \(P\) until the first time that the line meets some other point belonging to \(S\). This point, \(Q\), takes over as the new pivot, and the line now rotates clockwise about \(Q\), until it next meets a point of \(S\). This process continues indefinitely.

Show that we can choose a point \(P\) in \(S\) and a line \(\ell\) going through \(P\) such that the resulting windmill uses each point of \(S\) as a pivot infinitely many times.

Official text of the problem. Official problem paper (PDF)

Solution

Write \(n=|S|\). Choose a unit vector \(u_0\) such that the projections of the points of \(S\) onto \(u_0\) are all distinct. This is possible because only finitely many directions are perpendicular to a segment joining two points of \(S\). Label the points so that \[ u_0\cdot A_1<u_0\cdot A_2<\cdots<u_0\cdot A_n. \] Set \[ r=\left\lceil\frac n2\right\rceil. \] Start the windmill at \(P=A_r\), with \(\ell\) perpendicular to \(u_0\). By construction, \(\ell\) contains no other point of \(S\).

Parameterize the motion by its total clockwise angle of rotation \(t\), and let \(u(t)\) be \(u_0\) rotated clockwise through \(t\). If \(P(t)\) is the current pivot, the moving line has equation \[ u(t)\cdot X=c(t),\qquad c(t)=u(t)\cdot P(t). \] Call the side where \(u(t)\cdot X<c(t)\) the negative side.

The motion is well defined for arbitrarily large \(t\). Indeed, the next encounter occurs after a positive rotation of at most \(\pi\), and the point encountered is unique because no three points are collinear. Every encounter occurs at a direction parallel to a segment joining two points of \(S\). There are only finitely many such directions modulo \(\pi\), so only finitely many encounters can occur in any bounded interval of total rotation.

We claim that, except at the switching instants themselves, the negative side always contains exactly \(r-1\) points. This holds initially. Between switches, no point crosses the line. At a switch from pivot \(A\) to pivot \(B\), consider \[ f(t)=u(t)\cdot(B-A). \] This expression changes sign as the line rotates through \(AB\). Just before the switch, \(B\)'s signed position relative to the line is \(f(t)\); just after it, \(A\)'s signed position is \(-f(t)\). Thus \(A\) leaves the line on the same labeled side from which \(B\) approached. Every other point remains on its previous side, since no third point lies on \(AB\). The number of points on each side is therefore preserved, proving the claim.

Consequently, whenever the projections onto \(u(t)\) are all distinct, the pivot is the point with the \(r\)-th smallest projection.

After a half-turn, \[ u(\pi)=-u_0, \] so the projection order is reversed. Hence the pivot at \(t=\pi\) is \[ Q=A_{n+1-r}. \] The two indices \(r\) and \(n+1-r\) are equal when \(n\) is odd and consecutive when \(n\) is even. Therefore every point \(X\in S\setminus\{P,Q\}\) has its projection onto \(u_0\) either below both those of \(P,Q\), or above both.

For such a point \(X\), its signed positions at the two endpoints of this half-turn are \[ u_0\cdot(X-P) \quad\text{and}\quad -u_0\cdot(X-Q). \] They have opposite signs.

To justify that \(X\) must therefore meet the moving line, observe that \(c(t)\) is continuous: at a switch from \(A\) to \(B\), both lie on the same line, so \[ u(t)\cdot A=u(t)\cdot B. \] Thus \(u(t)\cdot X-c(t)\) is continuous. Its opposite endpoint signs force it to vanish somewhere during the half-turn. At that instant, \(X\) either is already the pivot or is the point encountered and becomes the new pivot.

The points \(P\) and \(Q\) are themselves pivots at the endpoints. We have therefore proved that every point of \(S\) is used as a pivot during the first half-turn, including when \(n=2\).

Finally, after a full turn, \(u(2\pi)=u_0\). The invariant forces the pivot to be \(A_r=P\), and the moving line is again \(\ell\). The windmill has returned to its initial state. Since each subsequent encounter is uniquely determined, the motion repeats after every full turn. Every point is consequently used as a pivot infinitely many times.

The solution was checked against the official IMO shortlist solutions.