Imo 2011

This is the wiki page for the mini-polymath3 project, which seeks solutions to Question 2 from the 2011 International Mathematical Olympiad.

The project started at July 19 8pm UTC, and is hosted at the polymath blog. A discussion thread is hosted at Terry Tao's blog.

Rules

This project will follow the usual polymath rules. In particular:

• Everyone is welcome to participate, though people who have already seen an external solution to the problem should refrain from giving spoilers throughout the experiment.
• This is a team effort, not a race between individuals. Rather than work for extended periods of time in isolation from the rest of the project, the idea is to come up with short observations (or to carry an observation of another participant further) and then report back what one gets to the rest of the team. Partial results or even failures can be worth reporting.
• Participants are encouraged to update the wiki, or to summarise progress within threads, for the benefit of others. (In particular, linking between the wiki and specific comments on the blogs is highly encouraged.)

Threads

Planning:

• Mini-polymath 3: 2011 IMO question, June 9 2011.

Discussion:

• Mini-polymath3 discussion thread, July 19 2011.

Research:

• Minipolymath3 project: 2011 IMO, July 19 2011

The question

Problem 2. Let [math]\displaystyle{ S }[/math] be a finite set of at least two points in the plane. Assume that no three points of [math]\displaystyle{ S }[/math] are collinear. A windmill is a process that starts with a line [math]\displaystyle{ \ell }[/math] going through a single point [math]\displaystyle{ P \in S }[/math]. The line rotates clockwise about the pivot [math]\displaystyle{ P }[/math] until the first time that the line meets some other point [math]\displaystyle{ Q }[/math] belonging to [math]\displaystyle{ S }[/math]. This point [math]\displaystyle{ Q }[/math] takes over as the new pivot, and the line now rotates clockwise about [math]\displaystyle{ Q }[/math], until it next meets a point of [math]\displaystyle{ S }[/math]. This process continues indefinitely.

Show that we can choose a point [math]\displaystyle{ P }[/math] in [math]\displaystyle{ S }[/math] and a line [math]\displaystyle{ \ell }[/math] going through [math]\displaystyle{ P }[/math] such that the resulting windmill uses each point of [math]\displaystyle{ S }[/math] as a pivot infinitely many times.

Observations and partial results

• Clarification: the rotating line extends out from a point in both directions, not just one direction (i.e. it is a full line, not a half line)
• Trivial observation: If we start with a point on the convex hull of S and a line l that is “tangent” to the convex hull then we will only iterate over the points from the convex hull.
• One can start with any point (since every point of S should be pivot infinitely often), the direction of line that one starts with however matters!
• As no three points are collinear, one can always find a line which splits the points into two sets whose number of elements differ at most one. One can find this no matter how we choose the first point. Then in some time the windmill must be parallel to the line through these points. This line must be unique or else it splits the points such that number of elements differ at least two.
• The process is time reversible, thus there are no “rho” processes with an initial segment that doesn't repeat. In particular, it’s enough to find a cycle that visits each vertex at least once.
• Since there are infinite many iterations and only finitely many essentially distinct configurations, all windmills must be part of a cycle.
• It appears that the number of points to the "left" or "right" of the line is constant through the entire process.
  • In particular, there must be n/2 distinct cycles since the number of points to the left or right of the line remains constant throughout the process.

Examples

• If the points form a convex polygon, it is easy.

• Say there are four points: an equilateral triangle A,B,C, and then one point M in the center of the triangle. No three points are collinear. If you start in M, you first hit say A, then C, then M, then B, then A.

• Place many equidistant points on a circle, and also take the center. Then, start with the line which uses two adjacent points on the convex hull, but with the line turning inwards rather than outwards (i.e., so that it does *not* just loop over the convex hull). This creates a loop that avoids the center.

Possible strategies

• Maybe the strategy should be to take out the convex hull of S from consideration; follow it up by induction on removing successive convex hulls.
• A possible line of enquiry might be to consider how adding additional points effects an already established “windmill” this might lead to an inductive solution if adding new points can be related to already established cases.
• It might be fun to use projective duality: the space of unoriented lines in the plane is diffeomorphic to the projective plane minus a point, i.e. the open Möbius strip, which I’ll call M. Every point p of S corresponds to a line m_p in M, and every line l passing through p in the plane corresponds to a point n_l on m_p in M. So the projective dual windmill process tracks the position of a point on the arrangement of lines in M dual to the points of S. The process begins with n_l on a line m_p and I suppose the clockwise direction tells us which direction we progress along m_p. I think the goal is then to show that there exists a starting point on the arrangement such that the trace of the projective dual windmill “curve” will hit every single line in this arrangement…?
• It seems that a good place to start is with the set, A, of ordered pairs of points, with each ordered pair representing a “transition” from one pivot point to the next. Each member of A would be a vertex in a directed graph containing an edge from each “transition” to its successor “transition”. One would then need to show that a cycle exists in this graph for which every point participates in at least one (actually two) of the vertices.
• Let's think about star polygons. For now say we have 2k+1 points on a circle. Connecting lines that have (k-1) points on one side and (k) points on the other side, results in a star that shows a way that windmill can swipe the whole space. If another point appears inside the body of the star, it seems it does not change the behavior of windmill that much. If a point appears outside the body of star, it should be possible to add that point as a vertex to the star too. So maybe an algorithmic way of adding points at a time to a star and see if the star includes all the points.

Completed solutions

• Start with a line which separates the points into two parts of roughly same size (their cardinal differ by at most one, not counting the point to which the line is attached). Then run the process until the line is “upside-down”, and so has turn by exactly $\pi$. Every point has gone from the right of the line to the left of the line (easy to see is the number of point is odd, you have to be a bit more crafty if it is even), and no point can go from left to right or right to left without touching the line. Add the previous remarks (the process will always come back to its initial configuration), and every point will be visited infinitely often.
  • I do not see how this solves the problem. When the line is "upside-down" (in terms of the angle) the pivot can be a different point, so the lines are not the same.
    • OK, I got it. The number of points on both sides of line stays constant, so when the line is "upside-down" the pivot is the original point or a point next to the original point.
  • Since this tripped me up for a while, a more complete explanation of why the number of points on both sides of the line stays constant: suppose for visualization that the line is horizontal and is just about to strike a new point. If the new point is to the right of the pivot, it must be below the line, and when it becomes the pivot the current pivot will end up below the line; likewise if the new point is to the left of the pivot.