The unexpectedly hard windmill question (2011 IMO, Q2)

Every year, more than 100 countries send six of their brightest teenagers, or the occasional prepubescent prodigy, to represent them at the International Math Olympiad, commonly known as the IMO. Considering that each country has its own elaborate system of contests leading to their choice of six representatives, the IMO stands as the culminating symbol for the surprisingly expansive and wonderful world that is contest math. The contest itself is essentially a test, split over two days, with three questions given over four and a half hours each day. The questions are all proofs, meaning you don't simply find some numerical answer, you have to discover and articulate a rigorous line of reasoning to answer each difficult question, and then each one is scored on a scale from 0 up to 7. Of interest to you and me today is the one from 2011, with 563 total participants representing 101 countries. I know what you're thinking, and the answer is yes, those do all happen to be prime numbers. But that's not why this test was interesting. Out of all these prime problem solvers, only one of them, Lisa Sauermann from Germany, got a perfect score. And the only thing standing between the next two runners up that year and a perfect score was problem number two. And this problem is beautiful, and despite evading many of the world's best mathematicians of their age, the solution is something that anyone watching this video can understand. So let's begin by reading through it carefully. Let S be a finite set of at least two points on the plane. Okay, so as you read the question it's often helpful to start drawing an example for yourself. Assume that no three points of S are collinear, in other words you never have three points lining up, so you can probably predict that the problem's going to involve drawing lines in some way that three points on one line would mess things up. A windmill is a process that starts with the line L going through a single point P in S. The line rotates clockwise around the pivot P until the first time that line meets some other point belonging to S. And again, while reading it's helpful to draw out an example so we've got this line that's pivoting around some point until it hits another. This point, Q, takes over as the new pivot, and the line now rotates clockwise about Q until it next meets a point of S. This process continues indefinitely. Alright, that's kind of fun. We keep rotating and changing the pivot, and you can see why they call it a windmill process, and you can also see why they specified that no three points lie on one line. You wouldn't want to run into the ambiguity where you don't know which pivot to switch to. Okay, so with all this setup, what's the question? Show that we can choose a point P in S and a line L going through P such that the resulting windmill uses each point of S as a pivot infinitely many times. Alright, depending on your tolerance of puzzles for puzzle's sake, you might wonder why would anyone care about such a question? There's a very good reason, in fact. I would argue that the act of solving this will make you better at math and related fields, and I'll explain why once you've seen the solution. But certainly on the surface, it feels disconnected from other parts of math. I mean, you look at other Olympiad problems, and they often involve some function to analyze, or a numerical pattern to deduce, maybe a difficult counting setup or an elaborate geometric construction. But problem two, it's an unusually pure puzzle, and in some ways that's its charm. Proving that some initial condition will result in this windmill hitting all the points infinitely many times, well that doesn't test your knowledge of a particular theorem. It tests if you can find a clever perspective. But that blade cuts both ways. Without resting on an existing result from math, what could possibly prepare someone to study for something like this? And in fact, that brings us to the second unusual thing about this problem.

Based on the results, I'm guessing that it turned out to be much harder than the contest organizers expected. You see, typically the three problems each day are supposed to get progressively harder. They're all hard, of course, it's the IMO, but problems one and four should be doable. Problems two and five, they're challenging. And problems three and six, well they can be brutal. But take a look at how many of our 563 participants that year got perfect scores on each of the problems. Only 22 of them got full marks for question number two. By contrast, 170 got a perfect score on problem five, which is supposed to be about the same difficulty, and more than twice as many got a perfect score for problem three, which is supposed to be harder. Some of you might notice that only six students got full points for problem six that year, so by some measure that was the hardest problem on the test. In fact, the way I introduced things earlier was a little disingenuous, the full data would suggest that problem six was the real clincher. But what's strange is that if you look at the results of those six students who solved this hardest problem, all of whom are clearly phenomenal world-class problem solvers, this windmill puzzle evaded five out of six of them. But again, this problem is not hard because of the background knowledge it demands, it asks only for insight. So how do you approach something like this? The first step with any puzzle is to simply play around with it and get a feel for it

and it's always good to start simple and slowly get more complicated from there. The simplest case would be two points, where the line trades off between each point. That works well enough. Adding a third point, it's pretty clear that the line will just rotate around them. It might not be entirely clear how you would phrase this as a rigorous proof yet, but right now we're just getting a feel for things. The fourth point is where it gets interesting. In some places, your windmill will go around the four points just like it did with the triangle, but if we put it inside that triangle, it looks like our windmill never hits it. Looking back at the problem, it's asking you to show that for some starting position of the line, not any position, the process will hit all the points infinitely many times. So for an example like this, if you start with the line going through that troublesome middle point, what happens? And again, at this point we're just playing around, perhaps moving your pencil among dots that you've drawn on a piece of scratch paper. You want to believe a result before you try too hard to prove it. Here you'd see that your windmill does indeed bounce off of all the points as it goes through a cycle, and it ends up back where it started. The worry you might have is that in some large sets of points, where some are kind of inside the others, you might be able to start off on the inside, but maybe something about this windmill process takes the line to the outside, where as time goes on to infinity it'll be blocked off from those inner points. If you play around, and mind you it can take some time to draw out many examples and think this through, you would notice that when the line starts off passing through the middle of the points, it tends to stay there. It never seems to venture off to the outside. But can you guarantee that this will always happen? Or rather, can you first make this idea of starting in the middle a little more rigorous, and from there prove that all the points will be hit infinitely many times? As a general problem-solving tip, whenever you have a vague idea that feels productive, you should of course find a way to be more exact about what you're saying, but preferably put numbers to it, and then see if you can ask questions about those numbers. In our example, one way to formalize this idea of a middle is to count how many points are on either side of the line. If you give the line some orientation, you can reasonably talk about a left half, say coloring all the points on the left blue, and a right right brown. And what it means for a line to be in the middle is that there are as many blue points as there are brown points. For the moment, let's say that the total number of points is an odd number, and the point that the line passes through is colored white, sort of a neutral color. So for example, if there were 11 points, you would have 5 blue ones on the left, 5 brown ones on the right, and the single white point as the pivot. The case with an even number of points will be similar, just slightly less symmetric. What this gives us is a new question to ask. What happens to the number of blue points and brown points as the process plays out? In the example on screen now, you might notice it's always 5 and 5, never changing. Playing around with other examples, you would find that the same is true. Take a moment to pause right now, and see if you can think through why exactly that would happen. Why would these numbers not change? Well, the key is to think through what happens as the line changes its pivot. Having given the line an orientation, we can talk reasonably about which half is above the pivot, and which one is below. If the line hits a blue point on its left, it must happen below the pivot. So then when it changes the pivot and continues rotating clockwise a bit, that old pivot, now above the new one, ends up to the left, meaning it ends up in the blue region. And entirely symmetrically, when it hits a brown point, it happens above the pivot, meaning that the old pivot ends up in the brown region. So no matter what, the number of points on a given side of the line cannot change, except for the instances where the line is passing through two points at once. When you lose a blue point, you gain a new one. When you lose a brown And that is our key insight number one. So why would this imply that the line must hit every point infinitely many times, no matter what weird set of points you could dream up? The second key is to think about letting this process go until the line has turned 180 degrees around. What that means is that it's parallel to the starting position, and because it has to remain the case that half the points are on one side and the other, it must be passing through the same point it started on. I mean, think about it, if it ended up on some other point, it would change the number on a given side. Additionally, since the line has rotated halfway around, everything that was blue has become brown, and everything which was brown has become blue, and the only way to change the color is if you get hit by the line. So for our odd-numbered case, that means that after a half rotation, the line is back where it started, and it's hit all of the other points. So as time goes forward, it repeats this exact set of motions over and over, hitting all of those points infinitely many times. For the case with an even number of points, we need to alter the scheme slightly, but only slightly. To make it so that the number of blues can equal the number of browns, let's say that the pivot counts now as a brown point. So to define our initial condition, we still say for a given angle of the line, select an initial point so that half of the points are blue, all on the left, and half of them are brown, now either meaning they're on the right, or the pivot. The same argument from before implies that after a 180° turn, everything has swapped colors, but this time the line will be passing through a different point after that first half turn, specifically one that used to be blue, but after another 180° it has to be passing through the one that it started on. Again, the logic is that it's parallel to its starting position, and if it was passing through any other point, the number of points on a given side would have to be different. So once more, we have a cycle which hits all of the points, and which ends in the same position where it started. This time it takes 360°, but that doesn't matter, as the cycle continues it'll hit all the points infinitely many times.

Stepping back, there are two important lessons to take away from this puzzle, the first one social and the second one mathematical. Once you know this solution, and if you ponder it a bit and turn it around in your head a couple times, it's very easy to fool yourself into thinking that the problem is easier than it is. After all, of course the number of points on a given side stays constant, right? Of course that's a question you would ask. And of course when you start in the middle, every point will switch sides after a half a turn. But the advantage of this problem coming from the IMO is that we don't have to rest on In the subject of statements, we have the data to show it's a genuinely hard problem, in that it evaded many of the world's best students who are demonstrably able to solve hard problems. In math, it's extremely hard to empathize with what it feels like to not understand something. I was discussing this video with a former coworker of mine from Khan Academy, who worked a lot with people creating math exercises, and he pointed out that across a wide variety of contributors, there's one constant. Nobody is able to tell how difficult their exercises are. Knowing when math is hard is way harder than the math itself. This is important to keep in mind when teaching, but it's equally being taught. On our windmill puzzle, even if counting the number of points on one side seems obvious in hindsight, you have to ask, given the vast space of possible things you might consider, Why would anyone's mind turn to that particular idea? This brings us to the mathematical takeaway. What ultimately led to the solution was finding something about the complex system which stays constant during this chaotic unfolding. This is a ubiquitous theme through math, and especially through physics. We're finding what's called an invariant. Topologists do this when they count the number of holes in a surface. Physicists do this when they define the ideas of energy and momentum, or in special relativity when they define more abstract ideas like proper time. As a student, it's easy to take for granted the definitions handed down to you, but the more puzzles you solve where the insight involves an invariant, the more you come to appreciate that each one of these definitions was once a clever discovery. Terence Tao, one of the greatest modern mathematicians and the world's youngest IMO medalist, wrote that mathematical problems or puzzles are important to real mathematics, like solving real-life problems, just as fables, stories, and anecdotes are important to the young in understanding real life. Sure, these kinds of puzzles are contrived, but they carry lessons relevant to useful problems you may actually need to solve one day. Maybe it seems silly to liken this windmill puzzle to a fairy tale, a mathematical Aesop summarizing that the moral of the story is to seek quantities which stay constant. But some of you watching this will one day face a problem where finding an invariant reveals a slick solution, and you might even look like a genius for doing so. If a made-up windmill prepares you for a real problem, who cares that it's a fiction?