I solved it during the competition, as did one other on my team The solution sketch is as follows: For each point there is a line going through it that cuts the remaining points into two groups that differ in size at most 1. Take such a line. I claim it works. Let P be a point. There is such a line l through it. At some point, the windmill will be parallel to that line (COUNTING ORIENTATION.) At this point, it must be l, or else not both of them can split them in such a way (Remember, everything requires orientation.) In my opinion is very nice problem.

Does a convex hull helps?

mszew wrote: Does a convex hull helps? I only know solutions of two people but they both are same as mine.

There are ones that claim a solution that consider the convex hull of the midle (say: consider the first convex hull, take it and tepear. We are talking about the last convex hull). The claim is that all lines trought one vertex of that convex hull is one of the vertex we want. But it seams to fail, I don't know: my solution is the one told before (now you know 3 people : ) )

pythag011 wrote: For each point there is a line going through it that cuts the remaining points into two groups that differ in size at most 1. Take such a line. I claim it works. Let P be a point. There is such a line l through it. At some point, the windmill will be parallel to that line (COUNTING ORIENTATION.) At this point, it must be l, or else not both of them can split them in such a way (Remember, everything requires orientation.) A nice solution to a really nice problem. Whether this problem deserves to be IMO #2 might be a point of argument (In my humble opinion, it should probably have been switched with the more mundane #3), but this kind of problem that requires some sort of creativity, rather than routine methods, is what we should hope to see more on the IMO. Congrats to the proposer, and to those who solved the problem

I don't know whichever admin did this but it's not acceptable to delete a post without mentioning any excuse. Well, I am hoping that this was an accident, and waiting for an explanation. Probably what I remembered was this USAMO problem, http://www.artofproblemsolving.com/Forum/viewtopic.php?p=213018&sid=d2ffc20858331fc25d3a6de15929c8a7#p213018 and this famous one, that is also mentioned in the link I gave, Quote: Given $2n+2$ points in the plane, no three collinear, prove that two of them determine a line that separates $n$ of the points from the other $n$. Having spent time with either of these from before is obviously an advantage. The second problem above looks as a trivial step in the proof of the IMO problem, but trying to use those lines is considerably harder if one has not seen them before the contest.

Umut Varolgunes wrote: Having spent time with either of these from before is obviously an advantage. The second problem above looks as a trivial step in the proof of the IMO problem, but trying to use those lines is considerably harder if one has not seen them before the contest. While I certainly agree with you that having seen either of the problems you pointed out is an advantage, applying them to this IMO problem is still far from a trivial task. If those background problems gave contestants such a big head start, I would imagine that the USA team, having worked on that recent USAMO problem, would have solved this one without much difficulty. That isn't what happened. I also didn't think of that magical line even though I have seen both of the problems you mentioned. It is very difficult to propose problems which are so novel that contestants start working on them on equal grounds, and several IMO problems, past and present, have failed much more terribly than this one in that respect. I see the advantage as a reward for those who persevered in studying past problems rather than a sign that a problem doesn't deserve to be on the contest.

I did not say that this problem shouldn't have been asked, or that these two problems trivialize the problem. What I said was precisely that having these in mind is an advantage, which you seem to agree too. I also agree on that this is a nice problem, and it should have been asked as the 3rd problem.

Umut Varolgunes wrote: I did not say that this problem shouldn't have been asked, or that these two problems trivialize the problem. What I said was precisely that having these in mind is an advantage, which you seem to agree too. I also agree on that this is a nice problem, and it should have been asked as the 3rd problem. Yes, I misread part of what you said, so sorry about that. Now I completely agree with you.

I have an idea that may lead to a solution but I'm not sure if it works. At first, you take the Convex Hull and you call that polygon S1, then you take $S_1$ out of $S$ and you take the Convex Hull and call that polygon $S_2$, and keep doing that until you have $S_1, S_2, S_3, \dots, S_n$ and 0, 1 or 2 points left. Now we choose the line $l$ such that it contains points inside $S_1, S_2,\dots, S_n$. Now we move l until it meets one of the points of $S$, but only one, if it touches 2 points in $S$ we generate $l$ again with a different angle (it will still have points inside the polygons, in fact, it will contain segments inside the polygons) and start with process. Case 1: 0 points left after the last convex hull is removed: Sn is a polygon: It's easy to see that for every polygon $S_i$ then the line l will always have points inside that polygon because the only way to "get out" of the polygon ethis meeting two consecutive points $v_1$ and $v_2$ of the polygon and leaving the polygon but if it touches $v_1$ and then $v_2$ it means that $v_2$ comes first in clockwise order so the line will then go inside the polygon. (I'm not too good explaining my solutions in English if there's something you don't understand please let me know and I'll try to explain it again). As the angle of the line will rotate forever in clockwise order, then every point in $S_i$ will be met infinitely many times by the line for every polygon Si because there will be a pair of points $(v,w)$ such that the line will meet $v$ and $w$ at the same time infinitely many times (after the second time it meets them the same movements from the first time start again leading to a cicle) and in that cicle every point is met at least once (that's not very hard to prove) Case 2: 1 or 2 points left after the last convex hull is removed: In this case we use the same algorithm than in the previous case, we forget about that 1 or 2 points and we can see that every poin inside $S_n$ will be met at least once in the process. So we start with the process until one of the 1 or 2 points inside $S_n$ is met, if it's just one point the idea is the same because the line will rotate forever and a pair of points will be met twice, hence infinitely many times, so evey point in every polygon will be met infinitely many times and the point inside too. If there are two points inside then we must prove that both points will be met in the process, but that's easy because as both points are inside $S_n$, and the line has a segment inside $S_n$ at every moment, and the line reaches the same position infinitely many times, then both points will be met infinitely many times because between moments $M_1$ and $M_2$ where the line has the same position every point inside $S_n$ will be met by the line (it's easy to prove that so I won't do it unless someone asks me to do it). I'm not sure that my solution is 100% correct, I just think that the idea is correct but I don't know if I prooved it in a correct way.

To each oriented straight line $\ell$ meeting $\mathcal{S}$ in exactly one point $P$, associate the pair of numbers $\pi_{\ell,P} = (\rho, \lambda)$ of points from $\mathcal{S}$, other than $P$, lying on its right side, respectively left side (clearly $\rho + \lambda = |\mathcal{S}| - 1$). Our goal is to exhibit such a (fixed) pair $(\rho, \lambda)$ that to each point $P \in \mathcal{S}$ (called anchor) corresponds some distinguished line $\ell$ with $\pi_{\ell,P} = (\rho, \lambda)$. Then starting the windmill on one of these lines will fulfill the requirements, since except at the moment of changing pivots (when the line of the windmill passes through two points), the pair associated to the windmill line stays $(\rho, \lambda)$ (this is easily seen, by the very movement of the windmill). As said above, when the windmill line becomes parallel (and similarly oriented) with one of the distinguished lines, it will have to pass through its anchor point (because of the count of points given by $(\rho, \lambda)$). Thus, there is nothing magic about having a balanced pair $|\rho - \lambda| \leq 1$; for a convex formation we can use a $(0, |\mathcal{S}| - 1)$ pair; for a square containing a point (other than its centre) we can use a $(1,3)$ pair. However, a pair known to exist for all points of $\mathcal{S}$ is precisely such a balanced pair, by discrete continuity arguments. In fact the first paragraph even provides a way to measure the correctness of a different approach. Clearly, the lines of every windmill will (except at changing pivots) share a same pair $(\rho, \lambda)$, so for each of the points of $\mathcal{S}$ there must exist some line passing through, with associated pair that of the starting line of the windmill, otherwise such a faulty point will be skipped, and the proof fail. A final word. A windmill starting on a line $\ell$ through a point $P \in \mathcal{S}$, corresponding to the pair $\pi_{\ell,P}$, will pass precisely through those points and only those as pivots, for which there exists a line having associated the starting pair $\pi_{\ell,P}$.

To be frank, I do not see why, the previous post, say, shows that the windmill will pass through every point of $\mathcal{S}$ (but that's probably just me being very stupid). Here's a different approach to show that any path through the windmill is purely periodic: Reason on pairs of points consecutively visited by the windmill. There are but finitely many such pairs, so one pair must appear more than once. Moreover, it is easy to convince oneself that any pair of points consecutively visited by a windmill uniquely determines the windmill. Thence the process is purely periodic.

There cannot be two parallel lines, similarly oriented, passing through different points of $\mathcal{S}$, and having the same associated $(\rho,\lambda)$ pair of number of points situated on their right, respectively left sides. Therefore, since a windmill reaches (infinitely often) all orientations for its lines, and its lines are always around some pivot, the windmill line having the orientation of any of the distinguished lines must have as pivot that line's anchor point.

Thanks a lot.

This is a nice-story problem! I've just soft-deleted my post (I think my idea doesn't work easily)

This problem seems more interesting than the easy #1 and #3, but I am not able to understand it. Say we have a triangle $ABC$, and a point $P$ inside it (and suppose the points $A,B,C$ are in clockwise order). Then how will we get the required windmill passing through all four points - i.e. at what point/line should we start with? The only windmills I can find trace out either $ABC$, or $APC$,$BPC$,$APC$, and I think I have tried all possibilities so I am confused.

Imagine the triangle $ABC$ with basis $CB$ horizontal, apex $A$ above, and $P$ interior. Start the windmill with a horizontal line through $P$. I will describe the change of pivots and directions, as the line rotates clockwise. Pivot $P$ from horizontal to $PB$ - changes pivot to $B$; Pivot $B$ from $PB$ to $AB$ - changes pivot to $A$; Pivot $A$ from $AB$ to $AP$ - changes pivot to $P$; Pivot $P$ from $AP$ to $PC$ - changes pivot to $C$; Pivot $C$ from $PC$ to $BC$ - changes pivot to $B$; Pivot $B$ from $BC$ to $BP$ - changes pivot to $P$; Pivot $P$ from $BP$ to $PA$ - changes pivot to $A$; Pivot $A$ from $PA$ to $CA$ - changes pivot to $C$; Pivot $C$ from $CA$ to $CP$ - changes pivot to $P$; Pivot $P$ from $CP$ to horizontal - comes back to starting position, then cycles. In fact, any starting line through $P$ works; the only ones rotating just around $ABC$ are starting lines that pass through a vertex, leaving the whole triangle on one side - when the windmill just tours round the convex hull.

This is categorized as geometry problem, according to ~2:10 of this video http://www.youtube.com/imo2011#p/a/u/0/fRbtwCzCFvI

Raja Oktovin wrote: This is categorized as geometry problem, according to ~2:10 of this video http://www.youtube.com/imo2011#p/a/u/0/fRbtwCzCFvI This problem is Combinatorics, according to the shortlist.

pythag011 wrote: I solved it during the competition, as did one other on my team The solution sketch is as follows: For each point there is a line going through it that cuts the remaining points into two groups that differ in size at most 1. Take such a line. I claim it works. Let P be a point. There is such a line l through it. At some point, the windmill will be parallel to that line (COUNTING ORIENTATION.) At this point, it must be l, or else not both of them can split them in such a way (Remember, everything requires orientation.) In my opinion is very nice problem. What is the motivation for this problem and what part of the problem made it the hardest IMO #2/5 ever? Thank you very much!

Does anyone know how one would come up with such a solution? Thank you very much for all your help!

this problem can be solved by taking case of concave and convex polygon and then using basics of rotations

you are correct i have solved this problem and what you say is correct and i have proved it by taking various cases possible but it has also an alternate solution for one of the case

Hope this works... Amir Hossein wrote: 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. Proposed by Geoffrey Smith, United Kingdom Take any point $P \in \mathcal{S}$ and a line $\ell$ through $P$ such that the number of points of $\mathcal{S}$ on both half-planes differ by at most one. Note that this property is preserved even when the pivots have switched. Claim: Each point in $\mathcal{S}$ occurs as a pivot of this windmill. (Proof) Among all angles made by three points of $\mathcal{S}$, let $\theta$ be the smallest. After each operation, the angle made by the new line with the original increases by $\theta$ so eventually it completes a rotation. So, for any point $X \in \mathcal{S}$ there exists a state of the line $\ell$ when it hasn't "crossed" $X$, and another when it has. Thus, at some moment it passed through $X$ so $X$ was the pivot of the windmill then. $\square$ When a rotation is "nearly" complete; it crosses the starting point $P$. Right now, the pivot is $P$ and before switching pivots, it must returns to its original position. Hence, the process is periodic and each point occurs as a pivot infinitely often. $\blacksquare$

]Denote them $l_k$ and $l_m$ denote two lines When $l_k$ has taken a rotation(half) Such that one is parallel to other and passes through points $P\in\mathcal{S}$. Say there are even no of points in a plane $2m=16$ ,$m=8$ Then let the 2 lines be represented by pink ] and [ red ] when they are parallel they have one pivot each on them and thus $l_k$ have $7$ points on its side and $l_m$ too And now every point on them have interchanged And vice versa when they are moved halfly. (half rotation) $\theta$ ] if we have an odd no of points in a plane of form $2k+1$,$k\in\mathbb{N}$ Then $l_k=l_m$ for all $P\in\mathcal{S}$ Note, it is used for the invariant of modulus function $|l_m–l_k|\ge 1$

redacted

Can someone please give me a hint on how to solve the problem? I don't want to read the full sol rather a hint would be nice

TwilightZone wrote: Can someone please give me a hint on how to solve the problem? I don't want to read the full sol rather a hint would be nice Forget about convex hull or other common combinatorics methods. Just try to use your creativity

Note that the line $\ell$ splits the plane into two regions. Call a point good if it's in one region and bad if it is in the other. $~$ As $\ell$ rotates, the number of good points is constant and a point switches its goodness if and only if it was a pivot. Thus, we pick $\ell$ so that the number of good and bad points are as balanced as possible. In this way, after one hundred eighty degrees rotation of $\ell$, every point has switches state, so every point has been a pivot.

3Blue1Brown made a video on this same problem. I highly recommend watching; it’s a great video.

Pick any point $P$ and line $\ell$ which divides set $\mathcal S \backslash P$ onto two sets, whose cardinalities differ by at most $1$ - we call such line as a good. Notice that in process of windmill good line stays good. Imagine that one half-plane, formed by $\ell$ is black, other is white, and these half-planes turns with rotating of $\ell.$ Fix starting position $\ell '$ of $\ell$. Claim. $\ell$ makes a half-turn during the windmill. Proof. Every rotation between changing of pivot increases angle clockwise between $\ell '$ and $\ell$ by at least minimal angle formed by three points from $\mathcal S$, thus the conclusion $\Box$ Due to the claim, for every point $X\in \mathcal S$ there are moments, when it in white half-plane and in black one, therefore $\ell$ passes through $X$ at some moment. Moreover, when $\ell$ makes half-turn it become parallel to $\ell '$. But since these lines are good it follows $\ell =\ell '$. Therefore the process is periodic and we are done.

nice question nice solve wow!

admittedly the hardest part is choosing P Consider an arbitrary fixed line $l_0$ that $l$ is the same as at some point, and take the line l which splits {S} without $P\in l_0$ into two sets/regions B and W colored black and white, s.t. $||B|-|W||\le 1$, and make sure B and W stay fixed in the sense that they move along whatever is split by $l$. Now, note that the difference between B and W stays fixed, because the new point that turns into pivot, whichever region it was in, the old pivot goes into that region, taking it's place. The problem is now solved, because the line keeps rotating, and each point will occur in both the black and white regions due to the line rotating a net of 180 degrees at some point, meaning the line will pass through all points in S before going back to P; because there are a finite number of points in S, the line will eventually return to the P that $l_0$ passes through, and becomes periodic because it will be the same as $l_0$ at some point. Varying $l_0$ to pass through each of the points in S, $l$ will pass through each of them periodically, so infinitely.

Claim:The number of points on one side is constant. Proof: Consider the moment when the pivot changes from a point $P$ to another point $Q.$ When both of the points are on the windmill line, the points on one side decreases by 1, and stays the same on the other side of the line. When $P$ no longer is the pivot, it adds a point to the side which decreased in the number of points it contained. Now take a windmill which has an absolute difference of $1$ point on each side. Claim: Such a line always exists through any point. Proof: This is obviously true by continuity, if we rotate the line around the point. Claim: Eventually, the sequence of pivots must cycle. Proof: Given any two points $P$ and $Q,$ if the pivot point changes from $P$ to $Q,$ the next points in the the sequence of pivots will be always be the same, no matter the place in the sequence these points occur. Since there are finitely many pairs of points, by the Pigeonhole Principle, eventually some pair must be repeated eventually, leading to a cycle. Claim: For any line $\ell,$ in the cycle, there is a line which is a windmill, and is parallel to $\ell$ Proof: If we go around in a complete cycle, we will end up back to be windmill we started with. So, by continuity, we have proven the claim. The only possible windmill parallel to a certain windmill $\ell,$ where $\ell$ has the absolute difference of the number of points in $S$ on either side of it at most $1$ is $\ell.$ This is because, if we have a different windmill parallel to $\ell,$ the difference between the number of points on either side of that line will not be at most $1.$ \newline \newline So, if we start with such a line $\ell$ as a windmill, we must cycle back to $\ell.$ Also, for any point $P,$ there will be a windmill through $P$ parallel to $\ell.$ Hence, we will continue to cycle, and will thus hit every point infinitely many times.