IMO 2011 Problem 2
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.
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.
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.
- Tahmid Hasan
- Posts:665
- Joined:Thu Dec 09, 2010 5:34 pm
- Location:Khulna,Bangladesh.
Re: IMO 2011 Problem 2
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
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
বড় ভালবাসি তোমায়,মা
Re: IMO 2011 Problem 2
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
- Tahmid Hasan
- Posts:665
- Joined:Thu Dec 09, 2010 5:34 pm
- Location:Khulna,Bangladesh.
Re: IMO 2011 Problem 2
even if i take $P=I$ ,$p$ can be the pivot for only the first time.Na $L$ wrote:In that case take $P=I$. Then you will visit every point infinitely often.
still confused.
বড় ভালবাসি তোমায়,মা
Re: IMO 2011 Problem 2
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
- Tahmid Hasan
- Posts:665
- Joined:Thu Dec 09, 2010 5:34 pm
- Location:Khulna,Bangladesh.
Re: IMO 2011 Problem 2
got it and i think i may have an idea with induction.
thanks.
বড় ভালবাসি তোমায়,মা
Re: IMO 2011 Problem 2
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 :
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.
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
Use $L^AT_EX$, It makes our work a lot easier!
Nur Muhammad Shafiullah | Mahi
Re: IMO 2011 Problem 2
My solution (!) !
But this is, unfortunately, wrong! Find the bug!!
But this is, unfortunately, wrong! Find the bug!!
ধনঞ্জয় বিশ্বাস
-
- Posts:1
- Joined:Wed Sep 07, 2011 8:21 pm
Re: IMO 2011 Problem 2
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.