Difference between revisions of "2011 IMO Problems/Problem 2"

(Added the solution)
m (Solution: typo)
Line 7: Line 7:
 
In order to divide the set <math>\mathcal S</math> into two halves, define <math>n</math> so that <math>N=2n+1+d</math> where <math>d=0</math> for an odd number of points and <math>d=1</math> for an even number of points.
 
In order to divide the set <math>\mathcal S</math> into two halves, define <math>n</math> so that <math>N=2n+1+d</math> where <math>d=0</math> for an odd number of points and <math>d=1</math> for an even number of points.
  
Start the "windmill" process with the line <math>\ell</math> going vertically through the point <math>P_{n+1}</math>.  Attach a up-down direction to this line so that we can color all points as follows: Points to the left of <math>\ell</math> (with lower x-coordinates) are blue, the pivot point on <math>\ell</math> is white and point to the right of <math>\ell</math> (with higher x-coordinates) are red.  We have now <math>n</math> blue points, one white point and <math>n+d</math> red points.
+
Start the "windmill" process with the line <math>\ell</math> going vertically through the point <math>P_{n+1}</math>.  Attach a down-up direction to this line so that we can color all points as follows: Points to the left of <math>\ell</math> (with lower x-coordinates) are blue, the pivot point on <math>\ell</math> is white and point to the right of <math>\ell</math> (with higher x-coordinates) are red.  We have now <math>n</math> blue points, one white point and <math>n+d</math> red points.
  
 
After processing the "windmill" by 180 degrees, the line <math>\ell</math> goes vertically up-down.  Now, points with lower x-coordinates are to the right of <math>\ell</math> and colored red; points with higher x-coordinates are to the left of <math>\ell</math> and colored blue.
 
After processing the "windmill" by 180 degrees, the line <math>\ell</math> goes vertically up-down.  Now, points with lower x-coordinates are to the right of <math>\ell</math> and colored red; points with higher x-coordinates are to the left of <math>\ell</math> and colored blue.

Revision as of 11:49, 13 May 2014

Let $\mathcal{S}$ be a finite set of at least two points in the plane. Assume that no three points of $\mathcal S$ are collinear. A windmill is a process that starts with a line $\ell$ going through a single point $P \in \mathcal S$. The line rotates clockwise about the pivot $P$ until the first time that the line meets some other point belonging to $\mathcal 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 $\mathcal S$. This process continues indefinitely. Show that we can choose a point $P$ in $\mathcal S$ and a line $\ell$ going through $P$ such that the resulting windmill uses each point of $\mathcal S$ as a pivot infinitely many times.

Solution

Choose a coordinate system so that all points in $\mathcal S$ have distinct x-coordinates. Number the points $P_i=(x_i,y_i)$ of $\mathcal S$ by increasing x-coordinates: $x_1<x_2<\ldots<x_N$.

In order to divide the set $\mathcal S$ into two halves, define $n$ so that $N=2n+1+d$ where $d=0$ for an odd number of points and $d=1$ for an even number of points.

Start the "windmill" process with the line $\ell$ going vertically through the point $P_{n+1}$. Attach a down-up direction to this line so that we can color all points as follows: Points to the left of $\ell$ (with lower x-coordinates) are blue, the pivot point on $\ell$ is white and point to the right of $\ell$ (with higher x-coordinates) are red. We have now $n$ blue points, one white point and $n+d$ red points.

After processing the "windmill" by 180 degrees, the line $\ell$ goes vertically up-down. Now, points with lower x-coordinates are to the right of $\ell$ and colored red; points with higher x-coordinates are to the left of $\ell$ and colored blue.

Note that at each pivot exchange, the old pivot point enters the same side of $\ell$ where the new pivot point came from. This means that throughout the "windmill" process, the number of blue points and the number of red points stay constant, respectively: We still have $n$ blue points, one white point and $n+d$ red points. This means that the current pivot point is $P_n+d$.

Note that all blue and all red points changed their color from the start of the "windmill" process. This implies that every point was a pivot at some stage of the rotation.

For every 180 degrees of "windmill" rotation, the same argument applies: all colored points must change their color and hence be a pivot at some stage. Infinitely many rotations imply infinitely many color changes. This completes the proof.

See Also