IMO 2011 Problem 2

Discussion on International Mathematical Olympiad (IMO)
User avatar
Moon
Site Admin
Posts: 751
Joined: Tue Nov 02, 2010 7:52 pm
Location: Dhaka, Bangladesh
Contact:

IMO 2011 Problem 2

Unread post by Moon » Wed Jul 20, 2011 12:33 pm

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.
"Inspiration is needed in geometry, just as much as in poetry." -- Aleksandr Pushkin

Please install LaTeX fonts in your PC for better looking equations,
learn how to write equations, and don't forget to read Forum Guide and Rules.

User avatar
Tahmid Hasan
Posts: 665
Joined: Thu Dec 09, 2010 5:34 pm
Location: Khulna,Bangladesh.

Re: IMO 2011 Problem 2

Unread post by Tahmid Hasan » Wed Jul 20, 2011 5:26 pm

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 :confused:
বড় ভালবাসি তোমায়,মা

User avatar
nayel
Posts: 268
Joined: Tue Dec 07, 2010 7:38 pm
Location: Dhaka, Bangladesh or Cambridge, UK

Re: IMO 2011 Problem 2

Unread post by nayel » Wed Jul 20, 2011 6:28 pm

In that case take $P=I$. Then you will visit every point infinitely often.
"Everything should be made as simple as possible, but not simpler." - Albert Einstein

User avatar
Tahmid Hasan
Posts: 665
Joined: Thu Dec 09, 2010 5:34 pm
Location: Khulna,Bangladesh.

Re: IMO 2011 Problem 2

Unread post by Tahmid Hasan » Thu Jul 21, 2011 9:33 am

Na $L$ wrote: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.
বড় ভালবাসি তোমায়,মা

User avatar
nayel
Posts: 268
Joined: Tue Dec 07, 2010 7:38 pm
Location: Dhaka, Bangladesh or Cambridge, UK

Re: IMO 2011 Problem 2

Unread post by nayel » Thu Jul 21, 2011 10:35 am

No, it is a pivot an infinite number of times. Remember the line always rotates clockwise.
"Everything should be made as simple as possible, but not simpler." - Albert Einstein

User avatar
Tahmid Hasan
Posts: 665
Joined: Thu Dec 09, 2010 5:34 pm
Location: Khulna,Bangladesh.

Re: IMO 2011 Problem 2

Unread post by Tahmid Hasan » Thu Jul 21, 2011 2:33 pm

:oops:
got it and i think i may have an idea with induction.
thanks.
বড় ভালবাসি তোমায়,মা

User avatar
*Mahi*
Posts: 1175
Joined: Wed Dec 29, 2010 12:46 pm
Location: 23.786228,90.354974
Contact:

Re: IMO 2011 Problem 2

Unread post by *Mahi* » Thu Aug 25, 2011 6:45 pm

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.87 KiB) Downloaded 247 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.
Please read Forum Guide and Rules before you post.

Use $L^AT_EX$, It makes our work a lot easier!

Nur Muhammad Shafiullah | Mahi

Corei13
Posts: 153
Joined: Tue Dec 07, 2010 9:10 pm
Location: Chittagong

Re: IMO 2011 Problem 2

Unread post by Corei13 » Wed Sep 07, 2011 11:04 pm

My solution (!) ! :D

But this is, unfortunately, wrong! Find the bug!!
ধনঞ্জয় বিশ্বাস

Geoff Smith
Posts: 1
Joined: Wed Sep 07, 2011 8:21 pm

Re: IMO 2011 Problem 2

Unread post by Geoff Smith » Thu Sep 08, 2011 12:14 am

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.

Post Reply