Variation on the IMO 2011 windmill problem
This question references the "windmill" question C3 of the 2011 Int'l Math Olympiad, documented here, p. 32:
In the first solution case there are n points on each side of the initial line (an odd total number of points S including the pivot.) In the second, there are n points on one side and (n - 1) points on the other (an even total number of points S.)
My question: Is it necessary to start with the initial pivot and windmill line in this exact configuration (depending on the odd/even number S?)
Is it possible to solve the problem with, say, (n - 2) points on one side of the initial line? What is the maximum possible difference between the sum of points on either side that meets the conditions of the answer (i.e. each point is a windmill pivot infinitely often?
1 Answer
$\begingroup$(I'm assuming that you've read the windmill solution and are familiar with the concepts, like the invariance in the number of points on one side, existence of line given any point, and uniqueness of line given direction.)
The difference between the number of points is crucial to the solution, because it guarantees the existence of the line given any point.
As an extreme example, if we're given $n$ points, and we consider a line going through 1 pivot point, has 0 points on 1 side, and $n-1$ points on the other, it is clear that this line cannot intersect the (interior of the) convex hull of the points.
In particular, if the convex hull interior contains a point, then no such line can touch this point, and so this point cannot ever be the pivot.
In particular, with $n=4$ points, then the line with 0 points on 1 side and 3 points on the other, will not work for the case where the convex hull is a triangle, and the other point is inside. This shows that a difference of 3 points isn't enough.
Now, let's consider the case where we have a difference of 2 points. This necessitates that there are $ n = 2k+1$ points, and the line has 1 pivot point, $k-1$ points on one side, and $k+1$ points on the other.
Claim: For any arrangement of $n = 2k+1$ points, and any given point $P$, there exists a line which has $k$ points on one side, and $k$ points on the other.
Proof: This is shown in the solution to the windmill problem.
Claim: For any arrangement of $n = 2k+1$ points, and any given point $P$, there exists a line which has $k-1$ points on one side, and $k+1$ points on the other.
Proof: Take the line in the solution in the windmill problem, and let it rotate past 1 point. We now have $ k-1$ points on one side, and $k+1$ points on the other.
Claim: Given a oriented direction (not parallel to the vector defined by 2 points), there is a unique line that passes through 1 point, and has $k-1$ points on one side and $k+1$ points on the other.
Note that the "oriented direction" means that a line with $k+1$ points "on top" is different than a line with $k-1$ points "on top".
Proof: Take the line and slowly move it across all of the points. At some stage, we must have exactly $k-1$ points on one side, it passes through 1 pivot point, and hence has $k+1$ points on the other side.
Claim: Such a line satisfies the conditions of the windmill problem.
Proof: Repeat the solution. All that we needed was A) Existance of line through any given point and B) Uniqueness of line given direction, which was shown above.
Corollary: For odd $n$, we could use a difference of 2 points.
Hence, the answer to your question is 2.
Note: Where this argument breaks down for larger differences, is that we cannot guarantee the existence of a line which has $ k-2$ points on one side, and $k+2$ points on the other. What this means is that as we rotate a line through this point, it toggles between having $k, k $ points and $ k-1, k+1 $ points.
Can you find such a configuration where there isn't a line with $k-2, k+2$ fo a given point?
Similarly, for $n = 2k$ even, there is a configuration where the line though the point always has $k-1, k$ points.
$\endgroup$ 2
