IMO 2011 Problem 2

[Moon]

Let $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.

[Tahmid Hasan]

i have a problem with this problem!!
what happens when four points $A,B,C,D,I$ chosen such that $A,B,C$ are vertexes of a triangle and $I$ a point in the interior.then $I$ can be the pivot for at most once.
a contradiction

[nayel]

In that case take $P=I$. Then you will visit every point infinitely often.

[Tahmid Hasan]

In that case take $P=I$. Then you will visit every point infinitely often.

even if i take $P=I$ ,$p$ can be the pivot for only the first time.
still confused.

[nayel]

No, it is a pivot an infinite number of times. Remember the line always rotates clockwise.

[Tahmid Hasan]

got it and i think i may have an idea with induction.
thanks.

[*Mahi*]

Guess I'm back , after that winding pre-test exam and untimely chicken pox. I hope I'd be able to be regular here now.

solution 2.pdf

This is the solution in PDF format ,if it's needed to be downloaded.

(449.87KiB)Downloaded 342 times

Solution :

We will proof the claim using induction. As the first step of induction, set $S$ with one, two or three points can be covered by a windmill by choosing any point and any line. So this is done.
Now we assume that every set $S$ with $m-1$ points has a windmill passing through all of them infinitely many times. Now we take a set of points $S$ with $m$ points in it. Let’s assume that there is no windmill which passes through all of them infinitely many times. But by our assumption there is a windmill passing through every possible $m-1$ points. So there are m windmills passing through every possible set of $m-1$ points.
Now we define a blade $P_iP_j$ when a windmill starts to rotate from line $P_iP_j$ centered in point $P_j$. So when the line touches another point $P_k$ the line becomes blade $P_jP_k$.
Now we can see that defining a blade defines a windmill. Now a windmill is built with blades and by the definition of a windmill, the process will never stop. As there is a limited number of blades $m(m-1)$ , so for any windmill at least a blade must repeat itself, and when a blade is repeated, the point before and after this must be repeated. So for any windmill process, it must be a cycle of blades.
Now there can be $m(m-1)$ blades, so the total length of all the windmills must be less than or equal to $m(m-1)$ as if any blade appears in two windmills, they will become the same.
Now we start to use the induction. As there are $m$ windmills with $m-1$ points, there total length must be greater than or equal to $m(m-1)$ as the least length of a windmill with $m-1$ points must be $m-1$.
So combining these two arguments, we can say that the total length of windmills in a $S$ with $m$ points in which there is no windmill covering all the points is $m(m-1)$.
Now in a set $S$ which abides by the condition stated above, choosing any blade ensures a $m-1$ length windmill.
Simple observation gives us that for any set $S$, choosing a blade from the convex hull of points inside which all other points resides, gives a $k$ length cycle consisting of $k$ points. So it shows that for any set where the convex hull of points inside which all other points reside has number of points other than $m-1$ can’t abide by those rules. So we have to prove the case where there are $m-1$ points on the convex hull of points inside which all other points reside.
Now in this case it is easy to see that a windmill taken through the center point in a $S$ like that will ensure that the center point is visited multiple times before the cycle is completed, because if it doesn’t happen, then the cycle must be the one covering the convex hull.

[Corei13]

My solution (!) !

But this is, unfortunately, wrong! Find the bug!!

[Geoff Smith]

I agree that the given induction argument is broken, but thus far no-one seems to have posted a solution anywhere on the internet which argues correctly by means of induction on the number of points. Such a solution would be very interesting.