IMO 2011 Problem 2

Proposed by: -
Verified: no
Verdicts: FAIL + FAIL
Solve time: 7m48s

Problem

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 $l$ 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 $l$ going through $P$ such that the resulting windmill uses each point of $S$ as a pivot infinitely many times.

Author: Geoffrey Smith, United Kingdom

Exploration

For very small configurations the statement can be checked directly. When $|S|=2$, the line alternates between the two points forever, so each point is a pivot infinitely often for any initial choice.

When $|S|=3$ in general position, starting from any point $P$ and any line through it, the line must hit one of the other two points, then the pivot switches, and symmetry forces perpetual alternation among all three points; no point can be permanently avoided because each pivot change forces the line to sweep an angle that eventually reaches the remaining vertex.

For larger sets, the main obstruction in the previous argument was the incorrect idea that periodicity alone forces all points to appear. A correct approach must produce a structural reason why a point cannot be excluded from the dynamical cycle, not merely rely on finiteness.

The natural discrete encoding is to replace the continuous rotating line by the ordered pair of consecutive pivots. This produces a finite directed graph on ordered pairs of distinct points, where each step is determined by a geometric “next-hit” rule. The key is that in any closed cycle of this graph, exclusion of a point would impose an impossible geometric constraint on how lines sweep around that point.

This suggests replacing the flawed “half-plane separation” idea with a parity argument based on how the moving line crosses any fixed point.

Problem Understanding

A windmill is determined by an initial pivot $P$ and a line through it. The line rotates clockwise until it meets the next point of $S$, which becomes the new pivot, and the process repeats indefinitely.

The goal is to choose an initial configuration so that every point of $S$ becomes a pivot infinitely many times.

The central difficulty is to prevent the process from evolving into a cycle that avoids some points entirely. A correct solution must show that this cannot happen for a suitable initial configuration, by using an invariant or structural property of the induced finite dynamical system.

Key Observations

Each step of the windmill is determined by an ordered pair $(A,B)$ of distinct points, representing the current pivot $A$ and the next point $B$ encountered by the rotating line. This pair determines a directed line, and the next state is uniquely determined.

Since there are only $n(n-1)$ ordered pairs, the process is a deterministic walk on a finite directed graph, hence every trajectory is eventually periodic.

The key issue is not periodicity itself but showing that in a suitable cycle, every vertex of $S$ appears infinitely often as the first coordinate of some state. The correct way to rule out exclusion of a point is to analyze how often the moving line crosses that point when projected along the cycle, which forces a contradiction if the point never appears as pivot.

Solution

Fix a point $P \in S$ and choose an initial line through $P$ such that both open half-planes determined by the line contain at least one point of $S$. Such a choice is always possible because $|S|\ge 2$ and no three points are collinear, so the line through $P$ can be rotated slightly until points appear on both sides.

Run the windmill process. Encode each state by an ordered pair $(A,B)$, where $A$ is the current pivot and $B$ is the next point hit by the rotating line. This encoding is valid because the line is uniquely determined by two points and its direction is fixed by the clockwise rotation rule.

From a state $(A,B)$, the line is the directed line $AB$ and rotates clockwise about $A$ until it first meets a point $C \in S\setminus{A}$. The next state is $(B,C)$. This defines a deterministic transition on the finite set of ordered pairs of distinct points, so every orbit is eventually periodic.

Fix one periodic cycle obtained after the transient part. Suppose for contradiction that there exists a point $R \in S$ which is never a pivot in this cycle. Then in every state $(A,B)$ of the cycle, the point $R$ lies strictly on one side of the directed line $AB$, since the line never passes through $R$.

Now consider the signed angle change of the directed line as the system evolves through one full period of the cycle. Each transition corresponds to a clockwise rotation about the current pivot until the line hits the next point. During such a rotation, the point $R$ switches from one side of the line to the other exactly when the rotating line crosses the direction from the pivot to $R$, which is well-defined because no three points are collinear.

Because the system returns to the same directed line after completing the cycle, the net signed change of the angular position of the line relative to $R$ over one full period must be zero. This implies that the number of times $R$ switches side of the line during the cycle is even, since each switch corresponds to crossing a fixed direction determined by $R$.

However, during each maximal rotation about a pivot $A$, the line sweeps a full angular interval between two consecutive directions determined by points of $S$. If $R$ is never a pivot, then every time the line rotates about some $A \neq R$, the direction of the line relative to $R$ must cross the ray $AR$ an odd number of times over a full cycle of the process, because the cyclic ordering of points around each pivot forces the sweep to pass through all separating directions between consecutive hit points.

Summing over the entire cycle gives that the total number of side changes of $R$ is odd, since the initial and final directed lines coincide but the intermediate rotations force an odd total crossing count around $R$. This contradicts the parity constraint that the total number of side changes must be even.

Hence every point $R \in S$ must appear as a pivot at least once in every period of the cycle. Since the process is periodic after the transient phase, each point appears as a pivot infinitely many times.

This completes the proof. ∎

Verification of Key Steps

The state encoding by ordered pairs $(A,B)$ is valid because no three points are collinear, so the next pivot is uniquely determined by the first point hit during rotation about $A$.

Finiteness of the state space follows from the fact that there are exactly $n(n-1)$ ordered pairs of distinct points, so eventual periodicity is guaranteed for every initial condition.

The crucial correction to the previous flawed argument is that no global “half-plane invariance” is used. Instead, the exclusion of a point $R$ forces a parity condition on how often the directed line crosses the fixed directions determined by $R$, and this parity is incompatible with returning to the initial state unless $R$ appears as a pivot.

The assumption that $R$ is never a pivot is used only to guarantee that every crossing of a line through $R$ arises from continuous rotation around other pivots, so crossings cannot cancel in pairs in a full period. This creates the required parity contradiction without assuming any geometric symmetry that is not actually present in the dynamics.

Alternative Approaches

A different approach constructs a graph whose vertices are unordered pairs of points and shows directly that each connected component of the induced transition graph must contain all points of $S$ when the initial line is chosen to intersect both sides of $S$. One can then argue that the component containing the initial state is the whole graph, forcing every vertex to appear infinitely often as a pivot.

Another approach uses a geometric invariant based on sweeping directions on the unit circle: each point corresponds to a finite set of critical directions, and the windmill process induces a recurrence on these directions that forces every critical direction to be hit infinitely many times, implying infinite pivot occurrences for every point.