Many of you may know, I am very passionate about mathematics, and I have focused much of my life around this intriguing field of study. However, the general perception of math is not always in such a positive light - although perhaps an overly broad generalization, from what I hear, a lot of my classmates dread the subject and consider it merely a constant struggle to memorize a bunch of cryptic formulae. This is consistent with the portrayal of the subject in mainstream media.
However, math doesn’t have to be the form of torture that everyone around you might suggest it is. In this article, I will present to you a problem that demonstrates just how rewarding mathematics can really be, that I hope will change your perception of the subject.
IMO 2011, Problem 2
This problem comes from the 2011 edition of the International Mathematical Olympiad, the most prestigious mathematics competition for high school students. (Shameless plug, by the way, if you’re passionate about this sort of mathematics, consider participating in the Swiss Mathematical Olympiad, it’s life-changing, true from experience.)
The problem goes as follows: let’s say you have n points in the plane, with the property that we cannot choose three of these points that lie on the same line. We will perform a process as follows: we choose one of the points, call it P, as well as a line that passes through P. Call P the pivot point. Now we will rotate the line clockwise around P until it goes through some point other than P, say Q, at which point we will switch the pivot to Q (without changing the line), and continue the process. The goal in this problem is to show that we can choose the initial pivot P, as well as the line through it, so that in performing this process forever, every one of the n points is used as a pivot an infinite number of times (each).
Here’s a visualization of the process:
By the way, this problem is superb and if you find the solution yourself (which I certainly didn’t) you’ll feel incredibly satisfied with yourself, so if you want to try solving the problem yourself first, do not scroll further.
The statement of this problem looks quite intimidating - the line appears to move around in an unpredictable manner. Who’s to say that the pivots can really behave in a regular enough manner to cycle through every point over and over? Let’s try to deconstruct the situation a bit.
Firstly, it doesn’t look like a point can ever just move over the line - intuitively, if a point “tried” to do so, it would by the definition of our process become a pivot instead. This means that the number of points on each side of the pivot never changes throughout the process (in jargon this means the number of points on each side is an invariant).
This motivates us to consider an approach where we cleverly fix the number of points on either side. Maybe we can balance it out? To simplify things, assume n is odd and write it as 2k+1, that way there is an even number of points other than the pivot at any given time. The case where n is even is not that different, and for space reasons, I won’t write about it here.
Choose any point P to be the initial pivot. Now, it turns out that it’s actually possible to choose a line through P that splits the plane in such a way that either side of the line has k points, as in the visualization above. Brief explanation: assign colors to the two sides of the line, say black and white. Say that initially, the black side has k+x points whereas the white side has k-x points. If we now rotate the line by 180 degrees, then now the sides will be flipped, i.e. the black side has k-x points. Now note that as we rotate the line, there is no way that the number of points on the black side can change by more than one at a time, because no three points lie on the same line. That is to say, the point count on the black side attains all values between k-x and k+x. In particular, it’s k at some point.
If we can show that this process uses every point as a pivot an infinite number of times, we will be very happy. Let us hence endeavor to prove this statement. Intuitively, having a line that exactly splits the set of points is unlikely, so there must be some important property that defines such lines. More formally, the key aspect to note is that if we fix what angle the line makes with the horizontal, there is only one way to place the line so that either side of it has k points. It’s to pass it through one of the n points because otherwise one of the sides would have more than k points. Now, as we rotate the line, it will attain all possible angles with the horizontal. Let Q be any one of the n points; we endeavor to show that Q is a pivot at some point. Take some line through Q whose two sides each contain k points. At some point “the line” will be parallel to it, so as noted above, the line absolutely has to pass through Q; that’s the only way we can satisfy the condition that either side has k points. This also implies that at some point, we will end up back at our original pivot with our original line. We are now finished, because every point is used as a pivot at least once, and the process is just an infinite loop of a cycle through all points.
Conclusion
The solution to IMO 2011, problem 2 is actually not that complicated; I strongly believe that most secondary students can understand it (if you didn’t understand my explanation then that’s just my fault). However, this problem eluded the vast majority of the world’s top math students during the 2011 contest and is considered one of the hardest problems in the competition’s history, demonstrating the immense amount of creativity needed to get this problem right. The specific approach that solves the problem isn’t that complicated, but it’s only one of many, many possible paths to take. Coming up with this approach therefore requires creativity that can’t be gained from school math the way it’s taught around the world today. And before you ask, yes, that’s math. Just because it isn’t algebraic or it doesn’t include long arithmetic calculations doesn’t invalidate the fact that it’s math. That’s the other popular misconception I wanted to clear in this article.
So, hopefully, you’re now more convinced about the creativity that can lie within math problems and can use this knowledge to dissociate math from torture.
Here is the original article if some of the equations are not displaying properly on your device:
Comments