Revisiting Arc Midpoints in Complex Numbers

1. Synopsis

One of the major headaches of using complex numbers in olympiad geometry problems is dealing with square roots. In particular, it is nontrivial to express the incenter of a triangle inscribed in the unit circle in terms of its vertices.

The following lemma is the standard way to set up the arc midpoints of a triangle. It appears for example as part (a) of Lemma 6.23.

Theorem 1 (Arc midpoint setup for a triangle)

Let {ABC} be a triangle with circumcircle {\Gamma} and let {M_A}, {M_B}, {M_C} denote the arc midpoints of {\widehat{BC}} opposite {A}, {\widehat{CA}} opposite {B}, {\widehat{AB}} opposite {C}.

Suppose we view {\Gamma} as the unit circle in the complex plane. Then there exist complex numbers {x}, {y}, {z} such that {A = x^2}, {B = y^2}, {C = z^2}, and

\displaystyle M_A = -yz, \quad M_B = -zx, \quad M_C = -xy.

Theorem 1 is often used in combination with the following lemma, which lets one assign the incenter the coordinates {-(xy+yz+zx)} in the above notation.

Lemma 2 (The incenter is the orthocenter of opposite arc midpoints)

Let {ABC} be a triangle with circumcircle {\Gamma} and let {M_A}, {M_B}, {M_C} denote the arc midpoints of {\widehat{BC}} opposite {A}, {\widehat{CA}} opposite {B}, {\widehat{AB}} opposite {C}. Then the incenter of {\triangle ABC} coincides with the orthocenter of {\triangle M_A M_B M_C}.

Unfortunately, the proof of Theorem 1 in my textbook is wrong, and I cannot find a proof online (though I hear that Lemmas in Olympiad Geometry has a proof). So in this post I will give a correct proof of Theorem 1, which will hopefully also explain the mysterious introduction of the minus signs in the theorem statement. In addition I will give a version of the theorem valid for quadrilaterals.

2. A Word of Warning

I should at once warn the reader that Theorem 1 is an existence result, and thus must be applied carefully.

To see why this matters, consider the following problem, which appeared as problem 1 of the 2016 JMO.

Example 3 (JMO 2016, by Zuming feng)

The isosceles triangle {\triangle ABC}, with {AB=AC}, is inscribed in the circle {\omega}. Let {P} be a variable point on the arc {BC} that does not contain {A}, and let {I_B} and {I_C} denote the incenters of triangles {\triangle ABP} and {\triangle ACP}, respectively. Prove that as {P} varies, the circumcircle of triangle {\triangle PI_{B}I_{C}} passes through a fixed point.

By experimenting with the diagram, it is not hard to guess that the correct fixed point is the midpoint of arc {\widehat{BC}}, as seen in the figure below. One might be tempted to write {A = x^2}, {B = y^2}, {C = z^2}, {P = t^2} and assert the two incenters are {-(xy+yt+xt)} and {-(xz+zt+xt)}, and that the fixed point is {-yz}.

This is a mistake! If one applies Theorem 1 twice, then the choices of “square roots” of the common vertices {A} and {P} may not be compatible. In fact, they cannot be compatible, because the arc midpoint of {\widehat{AP}} opposite {B} is different from the arc midpoint of {\widehat{AP}} opposite {C}.

In fact, I claim this is not a minor issue that one can work around. This is because the claim that the circumcircle of {\triangle P I_B I_C} passes through the midpoint of arc {\widehat{BC}} is false if {P} lies on the arc on the same side as {A}! In that case it actually passes through {A} instead. Thus the truth of the problem really depends on the fact that the quadrilateral {ABPC} is convex, and any attempt with complex numbers must take this into account to have a chance of working.

3. Proof of the theorem for triangles

Fix {ABC} now, so we require {A = x^2}, {B = y^2}, {C = z^2}. There are {2^3 = 8} choices of square roots {x}, {y}, {z} we can take (differing by a sign); we wish to show one of them works.

We pick an arbitrary choice for {x} first. Then, of the two choices of {y}, we pick the one such that {-xy = M_C}. Similarly, for the two choices of {z}, we pick the one such that {-xz = M_B}. Our goal is to show that under these conditions, we have {M_A = -yz} again.

The main trick is to now consider the arc midpoint {\widehat{BAC}}, which we denote by {L}. It is easy to see that:

Lemma 4 (The isosceles trapezoid trick)

We have {\overline{AL} \parallel \overline{M_B M_C}} (both are perpendicular to the {\angle A} bisector). Thus {A L M_B M_C} is an isosceles trapezoid, and so { A \cdot L = M_B \cdot M_C }.

Thus, we have

\displaystyle L = \frac{M_B M_C}{A} = \frac{(-xz)(-xy)}{x^2} = +yz.

Thus

\displaystyle M_A = -L = -yz

as desired.

From this we can see why the minus signs are necessary.

Exercise 5

Show that Theorem 1 becomes false if we try to use {+yz}, {+zx}, {+xy} instead of {-yz}, {-zx}, {-xy}.

4. A version for quadrilaterals

We now return to the setting of a convex quadrilateral {ABPC} that we encountered in Example 3. Suppose we preserve the variables {x}, {y}, {z} that we were given from Theorem 1, but now add a fourth complex number {t} with {P = t^2}. How are the new arc midpoints determined? The following theorem answers this question.

Theorem 6 ({xytz} setup)

Let {ABPC} be a convex quadrilateral inscribed in the unit circle of the complex plane. Then we can choose complex numbers {x}, {y}, {z}, {t} such that {A = x^2}, {B = y^2}, {C = z^2}, {P = t^2} and:

  • The opposite arc midpoints {M_A}, {M_B}, {M_C} of triangle {ABC} are given by {-yz}, {-zx}, {-xy}, as before.
  • The midpoint of arc {\widehat{BP}} not including {A} or {C} is given by {+yt}.
  • The midpoint of arc {\widehat{CP}} not including {A} or {B} is given by {-zt}.
  • The midpoint of arc {\widehat{ABP}} is {+xt} and the midpoint of arc {\widehat{ACP}} is {-xt}.

This setup is summarized in the following figure.

Note that unlike Theorem 1, the four arcs cut out by the sides of {ABCP} do not all have the same sign (I chose {\widehat{BP}} to have coordinates {+yt}). This asymmetry is inevitable (see if you can understand why from the proof below).

Proof: We select {x}, {y}, {z} with Theorem 1. Now, pick a choice of {t} such that {+yt} is the arc midpoint of {\widehat{BP}} not containing {A} and {C}. Then the arc midpoint of {\widehat{CP}} not containing {A} or {B} is given by

\displaystyle \frac{z^2}{-yz} \cdot (+yt) = -zt.

On the other hand, the calculation of {-xt} for the midpoint of {\widehat{ABP}} follows by applying Lemma 4 again. (applied to triangle {ABP}). The midpoint of {\widehat{ACP}} is computed similarly. \Box

In other problems, the four vertices of the quadrilateral may play more symmetric roles and in that case it may be desirable to pick a setup in which the four vertices are labeled {ABCD} in order. By relabeling the letters in Theorem 6 one can prove the following alternate formulation.

Corollary 7

Let {ABCD} be a convex quadrilateral inscribed in the unit circle of the complex plane. Then we can choose complex numbers {a}, {b}, {c}, {d} such that {A = a^2}, {B = b^2}, {C = c^2}, {D = d^2} and:

  • The midpoints of {\widehat{AB}}, {\widehat{BC}}, {\widehat{CD}}, {\widehat{DA}} cut out by the sides of {ABCD} are {-ab}, {-bc}, {-cd}, {+da}.
  • The midpoints of {\widehat{ABC}} and {\widehat{BCD}} are {+ac} and {+bd}.
  • The midpoints of {\widehat{CDA}} and {\widehat{DAB}} are {-ac} and {-bd}.

To test the newfound theorem, here is a cute easy application.

Example 8 (Japanese theorem for cyclic quadrilaterals)

In a cyclic quadrilateral {ABCD}, the incenters of {\triangle ABC}, {\triangle BCD}, {\triangle CDA}, {\triangle DAB} are the vertices of a rectangle.

Advertisements

Lessons from Math Olympiads

In a previous post I tried to make the point that math olympiads should not be judged by their relevance to research mathematics. In doing so I failed to actually explain why I think math olympiads are a valuable experience for high schoolers, so I want to make amends here.

1. Summary

In high school I used to think that math contests were primarily meant to encourage contestants to study some math that is (much) more interesting than what’s typically shown in high school. While I still think this is one goal, and maybe it still is the primary goal in some people’s minds, I no longer believe this is the primary benefit.

My current belief is that there are two major benefits from math competitions:

  1. To build a social network for gifted high school students with similar interests.
  2. To provide a challenging experience that lets gifted students grow and develop intellectually.

I should at once disclaim that I do not claim these are the only purpose of mathematical olympiads. Indeed, mathematics is a beautiful subject and introducing competitors to this field of study is of course a great thing (in particular it was life-changing for me). But as I have said before, many alumni of math olympiads do not eventually become mathematicians, and so in my mind I would like to make the case that these alumni have gained a lot from the experience anyways.

2. Social experience

Now that we have email, Facebook, Art of Problem Solving, and whatnot, the math contest community is much larger and stronger than it’s ever been in the past. For the first time, it’s really possible to stay connected with other competitors throughout the entire year, rather than just seeing each other a handful of times during contest season. There’s literally group chats of contestants all over the country where people talk about math problems or the solar eclipse or share funny pictures or inside jokes or everything else. In many ways, being part of the high school math contest community is a lot like having access to the peer group at a top-tier university, except four years earlier.

There’s some concern that a competitive culture is unhealthy for the contestants. I want to make a brief defense here.

I really do think that the contest community is good at being collaborative rather than competitive. You can imagine a world where the competitors think about contests in terms of trying to get a better score than the other person. [1] That would not be a good world. But I think by and large the community is good at thinking about it as just trying to maximize their own score. The score of the person next to you isn’t supposed to matter (and thinking about it doesn’t help, anyways).

Put more bluntly, on contest day, you have one job: get full marks. [2]

Because we have a culture of this shape, we now get a group of talented students all working towards the same thing, rather than against one another. That’s what makes it possible to have a self-supportive community, and what makes it possible for the contestants to really become friends with each other.

I think the strongest contestants don’t even care about the results of contests other than the few really important ones (like USAMO/IMO). It is a long-running joke that the Harvard-MIT Math Tournament is secretly just a MOP reunion, and I personally see to it that this happens every year. [3]

I’ve also heard similar sentiments about ARML:

I enjoy ARML primarily based on the social part of the contest, and many people agree with me; the highlight of ARML for some people is the long bus ride to the contest. Indeed, I think of ARML primarily as a social event, with some mathematics to make it look like the participants are actually doing something important.

(Don’t tell the parents.)

3. Intellectual growth

My view is that if you spend a lot of time thinking or working about anything deep, then you will learn and grow from the experience, almost regardless of what that thing is at an object level. Take chess as an example — even though chess definitely has even fewer “real-life applications” than math, if you take anyone with a 2000+ rating I don’t think many of them would think that the time they invested into the game was wasted. [4]

Olympiad mathematics seems to be no exception to this. In fact the sheer depth and difficulty of the subject probably makes it a particularly good example. [5]

I’m now going to fill this section with a bunch of examples although I don’t claim the list is exhaustive. First, here are the ones that everyone talks about and more or less agrees on:

  • Learning how to think, because, well, that’s how you solve a contest problem.
  • Learning to work hard and not give up, because the contest is difficult and you will not win by accident; you need to actually go through a lot of training.
  • Dual to above, learning to give up on a problem, because sometime the problem really is too hard for you and you won’t solve it even if you spend another ten or twenty or fifty hours, and you have to learn to cut your losses. There is a balancing act here that I think really is best taught by experience, rather than the standard high-school moral cheerleading where you are supposed to “never give up” or something.
  • But also learning to be humble or to ask for help, which is a really hard thing for a lot of young contestants to do.
  • Learning to be patient, not only with solving problems but with the entire journey. You usually do not improve dramatically overnight.

Here are some others I also believe, but don’t hear as often.

  • Learning to be independent, because odds are your high-school math teacher won’t be able to help you with USAMO problems. Training for the highest level of contests is these days almost always done more or less independently. I think having the self-motivation to do the training yourself, as well as the capacity to essentially have to design your own training (making judgments on what to work on, et cetera) is itself a valuable cross-domain skill. (I’m a little sad sometimes that by teaching I deprive my students of the opportunity to practice this. It is a cost.)
  • Being able to work neatly, not because your parents told you to but because if you are sloppy then it will cost you points when you make small (or large) errors on IMO #1. Olympiad problems are difficult enough as is, and you do not want to let them become any harder because of your own sloppiness. (And there are definitely examples of olympiad problems which are impossible to solve if you are not organized.)
  • Being able to organize and write your thoughts well, because some olympiad problems are complex and requires putting together more than one lemma or idea together to solve. For this to work, you need to have the skill of putting together a lot of moving parts into a single coherent argument. Bonus points here if your audience is someone you care about (as opposed to a grader), because then you have to also worry about making the presentation as clean and natural as possible.

    These days, whenever I solve a problem I always take the time to write it up cleanly, because in the process of doing so I nearly always find ways that the solution can be made shorter or more elegant, or at least philosophically more natural. (I also often find my solution is wrong.) So it seems that the write-up process here is not merely about presenting the same math in different ways: the underlying math really does change. [6]

  • Thinking about how to learn. For example, the Art of Problem Solving forums are often filled with questions of the form “what should I do?”. Many older users find these questions obnoxious, but I find them desirable. I think being able to spend time pondering about what makes people improve or learn well is a good trait to develop, rather than mindlessly doing one book after another.

    Of course, many of the questions I referred to are poor, either with no real specific direction: often the questions are essentially “what book should I read?”, or “give me a exhaustive list of everything I should know”. But I think this is inevitable because these are people’s first attempts at understanding contest training. Just like the first difficult math contest you take often goes quite badly, the first time you try to think about learning, you will probably ask questions you will be embarrassed about in five years. My hope is that as these younger users get older and wiser, the questions and thoughts become mature as well. To this end I do not mind seeing people wobble on their first steps.

  • Being honest with your own understanding, particularly of fundamentals. When watching experienced contestants, you often see people solving problems using advanced techniques like Brianchon’s theorem or the n-1 equal value principle or whatever. It’s tempting to think that if you learn the names and statements of all these advanced techniques then you’ll be able to apply them too. But the reality is that these techniques are advanced for a reason: they are hard to use without mastery of fundamentals.

    This is something I definitely struggled with as a contestant: being forced to patiently learn all the fundamentals and not worry about the fancy stuff. To give an example, the 2011 JMO featured an inequality which was routine for experienced or well-trained contestants, but “almost impossible for people who either have not seen inequalities at all or just like to compile famous names in their proofs”. I was in the latter category, and tried to make up a solution using multivariable Jensen, whatever that meant. Only when I was older did I really understand what I was missing.

  • Dual to the above, once you begin to master something completely you start to learn what different depths of understanding feel like, and an appreciation for just how much effort goes into developing a mastery of something.
  • Being able to think about things which are not well-defined. This one often comes as a surprise to people, since math is a field which is known for its precision. But I still maintain that this a skill contests train for.

    A very simple example is a question like, “when should I use the probabilistic method?”. Yes, we know it’s good for existence questions, but can we say anything more about when we expect it to work? Well, one heuristic (not the only one) is “if a monkey could find it” — the idea that a randomly selected object “should” work. But obviously something like this can’t be subject to a (useful) formal definition that works 100% of the time, and there are plenty of contexts in which even informally this heuristic gives the wrong answer. So that’s an example of a vague and nebulous concept that’s nonetheless necessary in order to understanding the probabilistic method well.

    There are much more general examples one can say. What does it mean for a problem to “feel projective”? I can’t tell you a hard set of rules; you’ll have to do a bunch of examples and gain the intuition yourself. Why do I say this problem is “rigid”? Same answer. How do you tell which parts of this problem are natural, and which are artificial? How do you react if you have the feeling the problem gives you nothing to work with? How can you tell if you are making progress on a problem? Trying to figure out partial answers to these questions, even if they can’t be put in words, will go a long way in improving the mythical intuition that everyone knows is so important.

    It might not be unreasonable to say that by this point we are studying philosophy, and that’s exactly what I intend. When I teach now I often make a point of referring to the “morally correct” way of thinking about things, or making a point of explaining why X should be true, rather than just providing a proof. I find this type of philosophy interesting in its own right, but that is not the main reason I incorporate it into my teaching. I teach the philosophy now because it is necessary, because you will solve fewer problems without that understanding.

4. I think if you don’t do well, it’s better to you

But I think the most surprising benefit of math contests is that most participants won’t win. In high school everyone tells you that if you work hard you will succeed. The USAMO is a fantastic counterexample to this. Every year, there are exactly 12 winners on the USAMO. I can promise you there are far more than 12 people who work very hard every year with the hope of doing well on the USAMO. Some people think this is discouraging, but I find it desirable.

Let me tell you a story.

Back in September of 2015, I sneaked in to the parent’s talk at Math Prize for Girls, because Zuming Feng was speaking and I wanted to hear what he had to say. (The whole talk was is available on YouTube now.) The talk had a lot of different parts that I liked, but one of them struck me in particular, when he recounted something he said to one of his top students:

I really want you to work hard, but I really think if you don’t do well, if you fail, it’s better to you.

I had a hard time relating to this when I first heard it, but it makes sense if you think about it. What I’ve tried to argue is that the benefit of math contests is not that the contestant can now solve N problems on USAMO in late April, but what you gain from the entire year of practice. And so if you hold the other 363 days fixed, and then vary only the final outcome of the USAMO, which of success and failure is going to help a contestant develop more as a person?

For that reason I really like to think that the final lesson from high school olympiads is how to appreciate the entire journey, even in spite of the eventual outcome.

Footnotes

  1. I actually think this is one of the good arguments in favor of the new JMO/USAMO system introduced in 2010. Before this, it was not uncommon for participants in 9th and 10th grade to really only aim for solving one or two entry-level USAMO problems to qualify for MOP. To this end I think the mentality of “the cutoff will probably only be X, so give up on solving problem six” is sub-optimal.
  2. That’s a Zuming quote.
  3. Which is why I think the HMIC is actually sort of pointless from a contestant’s perspective, but it’s good logistics training for the tournament directors.
  4. I could be wrong about people thinking chess is a good experience, given that I don’t actually have any serious chess experience beyond knowing how the pieces move. A cursory scan of the Internet suggests otherwise (was surprised to find that Ben Franklin has an opinion on this) but it’s possible there are people who think chess is a waste of time, and are merely not as vocal as the people who think math contests are a waste of time.
  5. Relative to what many high school students work on, not compared to research or something.
  6. Privately, I think that working in math olympiads taught me way more about writing well than English class ever did; English class always felt to me like the skill of trying to sound like I was saying something substantial, even when I wasn’t.

Some Thoughts on Olympiad Material Design

(This is a bit of a follow-up to the solution reading post last month. Spoiler warnings: USAMO 2014/6, USAMO 2012/2, TSTST 2016/4, and hints for ELMO 2013/1, IMO 2016/2.)

I want to say a little about the process which I use to design my olympiad handouts and classes these days (and thus by extension the way I personally think about problems). The short summary is that my teaching style is centered around showing connections and recurring themes between problems.

Now let me explain this in more detail.

1. Main ideas

Solutions to olympiad problems can look quite different from one another at a surface level, but typically they center around one or two main ideas, as I describe in my post on reading solutions. Because details are easy to work out once you have the main idea, as far as learning is concerned you can more or less throw away the details and pay most of your attention to main ideas.

Thus whenever I solve an olympiad problem, I make a deliberate effort to summarize the solution in a few sentences, such that I basically know how to do it from there. I also make a deliberate effort, whenever I write up a solution in my notes, to structure it so that my future self can see all the key ideas at a glance and thus be able to understand the general path of the solution immediately.

The example I’ve previously mentioned is USAMO 2014/6.

Example 1 (USAMO 2014, Gabriel Dospinescu)

Prove that there is a constant {c>0} with the following property: If {a, b, n} are positive integers such that {\gcd(a+i, b+j)>1} for all {i, j \in \{0, 1, \dots, n\}}, then

\displaystyle  \min\{a, b\}> (cn)^n.

If you look at any complete solution to the problem, you will see a lot of technical estimates involving {\zeta(2)} and the like. But the main idea is very simple: “consider an {N \times N} table of primes and note the small primes cannot adequately cover the board, since {\sum p^{-2} < \frac{1}{2}}”. Once you have this main idea the technical estimates are just the grunt work that you force yourself to do if you’re a contestant (and don’t do if you’re retired like me).

Thus the study of olympiad problems is reduced to the study of main ideas behind these problems.

2. Taxonomy

So how do we come up with the main ideas? Of course I won’t be able to answer this question completely, because therein lies most of the difficulty of olympiads.

But I do have some progress in this way. It comes down to seeing how main ideas are similar to each other. I spend a lot of time trying to classify the main ideas into categories or themes, based on how similar they feel to one another. If I see one theme pop up over and over, then I can make it into a class.

I think olympiad taxonomy is severely underrated, and generally not done correctly. The status quo is that people do bucket sorts based on the particular technical details which are present in the problem. This is correlated with the main ideas, but the two do not always coincide.

An example where technical sort works okay is Euclidean geometry. Here is a simple example: harmonic bundles in projective geometry. As I explain in my book, there are a few “basic” configurations involved:

  • Midpoints and parallel lines
  • The Ceva / Menelaus configuration
  • Harmonic quadrilateral / symmedian configuration
  • Apollonian circle (right angle and bisectors)

(For a reference, see Lemmas 2, 4, 5 and Exercise 0 here.) Thus from experience, any time I see one of these pictures inside the current diagram, I think to myself that “this problem feels projective”; and if there is a way to do so I try to use harmonic bundles on it.

An example where technical sort fails is the “pigeonhole principle”. A typical problem in such a class looks something like USAMO 2012/2.

Example 2 (USAMO 2012, Gregory Galperin)

A circle is divided into congruent arcs by {432} points. The points are colored in four colors such that some {108} points are colored Red, some {108} points are colored Green, some {108} points are colored Blue, and the remaining {108} points are colored Yellow. Prove that one can choose three points of each color in such a way that the four triangles formed by the chosen points of the same color are congruent.

It’s true that the official solution uses the words “pigeonhole principle” but that is not really the heart of the matter; the key idea is that you consider all possible rotations and count the number of incidences. (In any case, such calculations are better done using expected value anyways.)

Now why is taxonomy a good thing for learning and teaching? The reason is that building connections and seeing similarities is most easily done by simultaneously presenting several related problems. I’ve actually mentioned this already in a different blog post, but let me give the demonstration again.

Suppose I wrote down the following:

\displaystyle  \begin{array}{lll} A1 & B11 & C8 \\ A9 & B44 & C27 \\ A49 & B33 & C343 \\ A16 & B99 & C1 \\ A25 & B22 & C125 \end{array}

You can tell what each of the {A}‘s, {B}‘s, {C}‘s have in common by looking for a few moments. But what happens if I intertwine them?

\displaystyle  \begin{array}{lllll} B11 & C27 & C343 & A1 & A9 \\ C125 & B33 & A49 & B44 & A25 \\ A16 & B99 & B22 & C8 & C1 \end{array}

This is the same information, but now you have to work much harder to notice the association between the letters and the numbers they’re next to.

This is why, if you are an olympiad student, I strongly encourage you to keep a journal or blog of the problems you’ve done. Solving olympiad problems takes lots of time and so it’s worth it to spend at least a few minutes jotting down the main ideas. And once you have enough of these, you can start to see new connections between problems you haven’t seen before, rather than being confined to thinking about individual problems in isolation. (Additionally, it means you will never have redo problems to which you forgot the solution — learn from my mistake here.)

3. Ten buckets of geometry

I want to elaborate more on geometry in general. These days, if I see a solution to a Euclidean geometry problem, then I mentally store the problem and solution into one (or more) buckets. I can even tell you what my buckets are:

  1. Direct angle chasing
  2. Power of a point / radical axis
  3. Homothety, similar triangles, ratios
  4. Recognizing some standard configuration (see Yufei for a list)
  5. Doing some length calculations
  6. Complex numbers
  7. Barycentric coordinates
  8. Inversion
  9. Harmonic bundles or pole/polar and homography
  10. Spiral similarity, Miquel points

which my dedicated fans probably recognize as the ten chapters of my textbook. (Problems may also fall in more than one bucket if for example they are difficult and require multiple key ideas, or if there are multiple solutions.)

Now whenever I see a new geometry problem, the diagram will often “feel” similar to problems in a certain bucket. Exactly what I mean by “feel” is hard to formalize — it’s a certain gut feeling that you pick up by doing enough examples. There are some things you can say, such as “problems which feature a central circle and feet of altitudes tend to fall in bucket 6”, or “problems which only involve incidence always fall in bucket 9”. But it seems hard to come up with an exhaustive list of hard rules that will do better than human intuition.

4. How do problems feel?

But as I said in my post on reading solutions, there are deeper lessons to teach than just technical details.

For examples of themes on opposite ends of the spectrum, let’s move on to combinatorics. Geometry is quite structured and so the themes in the main ideas tend to translate to specific theorems used in the solution. Combinatorics is much less structured and many of the themes I use in combinatorics cannot really be formalized. (Consequently, since everyone else seems to mostly teach technical themes, several of the combinatorics themes I teach are idiosyncratic, and to my knowledge are not taught by anyone else.)

For example, one of the unusual themes I teach is called Global. It’s about the idea that to solve a problem, you can just kind of “add up everything at once”, for example using linearity of expectation, or by double-counting, or whatever. In particular these kinds of approach ignore the “local” details of the problem. It’s hard to make this precise, so I’ll just give two recent examples.

Example 3 (ELMO 2013, Ray Li)

Let {a_1,a_2,\dots,a_9} be nine real numbers, not necessarily distinct, with average {m}. Let {A} denote the number of triples {1 \le i < j < k \le 9} for which {a_i + a_j + a_k \ge 3m}. What is the minimum possible value of {A}?

Example 4 (IMO 2016)

Find all integers {n} for which each cell of {n \times n} table can be filled with one of the letters {I}, {M} and {O} in such a way that:

  • In each row and column, one third of the entries are {I}, one third are {M} and one third are {O}; and
  • in any diagonal, if the number of entries on the diagonal is a multiple of three, then one third of the entries are {I}, one third are {M} and one third are {O}.

If you look at the solutions to these problems, they have the same “feeling” of adding everything up, even though the specific techniques are somewhat different (double-counting for the former, diagonals modulo {3} for the latter). Nonetheless, my experience with problems similar to the former was immensely helpful for the latter, and it’s why I was able to solve the IMO problem.

5. Gaps

This perspective also explains why I’m relatively bad at functional equations. There are some things I can say that may be useful (see my handouts), but much of the time these are just technical tricks. (When sorting functional equations in my head, I have a bucket called “standard fare” meaning that you “just do work”; as far I can tell this bucket is pretty useless.) I always feel stupid teaching functional equations, because I never have many good insights to say.

Part of the reason is that functional equations often don’t have a main idea at all. Consequently it’s hard for me to do useful taxonomy on them.

Then sometimes you run into something like the windmill problem, the solution of which is fairly “novel”, not being similar to problems that come up in training. I have yet to figure out a good way to train students to be able to solve windmill-like problems.

6. Surprise

I’ll close by mentioning one common way I come up with a theme.

Sometimes I will run across an olympiad problem {P} which I solve quickly, and think should be very easy, and yet once I start grading {P} I find that the scores are much lower than I expected. Since the way I solve problems is by drawing experience from similar previous problems, this must mean that I’ve subconsciously found a general framework to solve problems like {P}, which is not obvious to my students yet. So if I can put my finger on what that framework is, then I have something new to say.

The most recent example I can think of when this happened was TSTST 2016/4 which was given last June (and was also a very elegant problem, at least in my opinion).

Example 5 (TSTST 2016, Linus Hamilton)

Let {n > 1} be a positive integers. Prove that we must apply the Euler {\varphi} function at least {\log_3 n} times before reaching {1}.

I solved this problem very quickly when we were drafting the TSTST exam, figuring out the solution while walking to dinner. So I was quite surprised when I looked at the scores for the problem and found out that empirically it was not that easy.

After I thought about this, I have a new tentative idea. You see, when doing this problem I really was thinking about “what does this {\varphi} operation do?”. You can think of {n} as an infinite tuple

\displaystyle  \left(\nu_2(n), \nu_3(n), \nu_5(n), \nu_7(n), \dots \right)

of prime exponents. Then the {\varphi} can be thought of as an operation which takes each nonzero component, decreases it by one, and then adds some particular vector back. For example, if {\nu_7(n) > 0} then {\nu_7} is decreased by one and each of {\nu_2(n)} and {\nu_3(n)} are increased by one. In any case, if you look at this behavior for long enough you will see that the {\nu_2} coordinate is a natural way to “track time” in successive {\varphi} operations; once you figure this out, getting the bound of {\log_3 n} is quite natural. (Details left as exercise to reader.)

Now when I read through the solutions, I found that many of them had not really tried to think of the problem in such a “structured” way, and had tried to directly solve it by for example trying to prove {\varphi(n) \ge n/3} (which is false) or something similar to this. I realized that had the students just ignored the task “prove {n \le 3^k}” and spent some time getting a better understanding of the {\varphi} structure, they would have had a much better chance at solving the problem. Why had I known that structural thinking would be helpful? I couldn’t quite explain it, but it had something to do with the fact that the “main object” of the question was “set in stone”; there was no “degrees of freedom” in it, and it was concrete enough that I felt like I could understand it. Once I understood how multiple {\varphi} operations behaved, the bit about {\log_3 n} almost served as an “answer extraction” mechanism.

These thoughts led to the recent development of a class which I named Rigid, which is all about problems where the point is not to immediately try to prove what the question asks for, but to first step back and understand completely how a particular rigid structure (like the {\varphi} in this problem) behaves, and to then solve the problem using this understanding.

Formal vs Functional Series (OR: Generating Function Voodoo Magic)

Epistemic status: highly dubious. I found almost no literature doing anything quite like what follows, which unsettles me because it makes it likely that I’m overcomplicating things significantly.

1. Synopsis

Recently I was working on an elegant problem which was the original problem 6 for the 2015 International Math Olympiad, which reads as follows:

Problem

[IMO Shortlist 2015 Problem C6] Let {S} be a nonempty set of positive integers. We say that a positive integer {n} is clean if it has a unique representation as a sum of an odd number of distinct elements from {S}. Prove that there exist infinitely many positive integers that are not clean.

Proceeding by contradiction, one can prove (try it!) that in fact all sufficiently large integers have exactly one representation as a sum of an even subset of {S}. Then, the problem reduces to the following:

Problem

Show that if {s_1 < s_2 < \dots} is an increasing sequence of positive integers and {P(x)} is a nonzero polynomial then we cannot have

\displaystyle \prod_{j=1}^\infty (1 - x^{s_j}) = P(x)

as formal series.

To see this, note that all sufficiently large {x^N} have coefficient {1 + (-1) = 0}. Now, the intuitive idea is obvious: the root {1} appears with finite multiplicity in {P} so we can put {P(x) = (1-x)^k Q(x)} where {Q(1) \neq 0}, and then we get that {1-x} on the RHS divides {P} too many times, right?

Well, there are some obvious issues with this “proof”: for example, consider the equality

\displaystyle 1 = (1-x)(1+x)(1+x^2)(1+x^4)(1+x^8) \dots.

The right-hand side is “divisible” by {1-x}, but the left-hand side is not (as a polynomial).

But we still want to use the idea of plugging {x \rightarrow 1^-}, so what is the right thing to do? It turns out that this is a complete minefield, and there are a lot of very subtle distinctions that seem to not be explicitly mentioned in many places. I think I have a complete answer now, but it’s long enough to warrant this entire blog post.

Here’s the short version: there’s actually two distinct notions of “generating function”, namely a “formal series” and “functional series”. They use exactly the same notation but are two different types of objects, and this ends up being the source of lots of errors, because “formal series” do not allow substituting {x}, while “functional series” do.

Spoiler: we’ll need the asymptotic for the partition function {p(n)}.

2. Formal Series {\neq} Functional Series

I’m assuming you’ve all heard the definition of {\sum_k c_kx^k}. It turns out unfortunately that this isn’t everything: there are actually two types of objects at play here. They are usually called formal power series and power series, but for this post I will use the more descriptive names formal series and functional series. I’ll do everything over {\mathbb C}, but one can of course use {\mathbb R} instead.

The formal series is easier to describe:

Definition 1

A formal series {F} is an infinite sequence {(a_n)_n = (a_0, a_1, a_2, \dots)} of complex numbers. We often denote it by {\sum a_nx^n = a_0 + a_1x + a_2x^2 + \dots}. The set of formal series is denoted {\mathbb C[ [x] ]}.

This is the “algebraic” viewpoint: it’s a sequence of coefficients. Note that there is no worry about convergence issues or “plugging in {x}”.

On the other hand, a functional series is more involved, because it has to support substitution of values of {x} and worry about convergence issues. So here are the necessary pieces of data:

Definition 2

A functional series {G} (centered at zero) is a function {G : U \rightarrow \mathbb C}, where {U} is an open disk centered at {0} or {U = \mathbb C}. We require that there exists an infinite sequence {(c_0, c_1, c_2, \dots)} of complex numbers satisfying

\displaystyle \forall z \in U: \qquad G(z) = \lim_{N \rightarrow \infty} \left( \sum_{k=0}^N c_k z^k \right).

(The limit is take in the usual metric of {\mathbb C}.) In that case, the {c_i} are unique and called the coefficients of {G}.

This is often written as {G(x) = \sum_n c_n x^n}, with the open set {U} suppressed.

Remark 3

Some remarks on the definition of functional series:

  • This is enough to imply that {G} is holomorphic (and thus analytic) on {U}.
  • For experts: note that I’m including the domain {U} as part of the data required to specify {G}, which makes the presentation cleaner. Most sources do something with “radius of convergence”; I will blissfully ignore this, leaving this data implicitly captured by {U}.
  • For experts: Perhaps non-standard, {U \neq \{0\}}. Otherwise I can’t take derivatives, etc.

Thus formal and functional series, despite having the same notation, have different types: a formal series {F} is a sequence, while a functional series {G} is a function that happens to be expressible as an infinite sum within its domain.

Of course, from every functional series {G} we can extract its coefficients and make them into a formal series {F}. So, for lack of better notation:

Definition 4

If {F = (a_n)_n} is a formal series, and {G : U \rightarrow \mathbb C} is a functional series whose coefficients equal {F}, then we write {F \simeq G}.

3. Finite operations

Now that we have formal and functional series, we can define sums. Since these are different types of objects, we will have to run definitions in parallel and then ideally check that they respect {\simeq}.

For formal series:

Definition 5

Let {F_1 = (a_n)_n} and {F_2 = (b_n)_n} be formal series. Then we set

\displaystyle \begin{aligned} (a_n)_n \pm (b_n)_n &= (a_n \pm b_n)_n \\ (a_n)_n \cdot (b_n)_n &= \left( \textstyle\sum_{j=0}^n a_jb_{n-j} \right)_n. \end{aligned}

This makes {\mathbb C[ [x] ]} into a ring, with identity {(0,0,0,\dots)} and {(1,0,0,\dots)}.

We also define the derivative {F = (a_n)_n} by {F' = ((n+1)a_{n+1})_n}.

It’s probably more intuitive to write these definitions as

\displaystyle \begin{aligned} \sum_n a_n x^n \pm \sum_n b_n x^n &= \sum_n (a_n \pm b_n) x^n \\ \left( \sum_n a_n x^n \right) \left( \sum_n b_n x^n \right) &= \sum_n \left( \sum_{j=0}^n a_jb_{n-j} \right) x^n \\ \left( \sum_n a_n x^n \right)' &= \sum_n na_n x^{n-1} \end{aligned}

and in what follows I’ll start to use {\sum_n a_nx^n} more. But officially, all definitions for formal series are in terms of the coefficients alone; these presence of {x} serves as motivation only.

Exercise 6

Show that if {F = \sum_n a_nx^n} is a formal series, then it has a multiplicative inverse if and only if {a_0 \neq 0}.

On the other hand, with functional series, the above operations are even simpler:

Definition 7

Let {G_1 : U \rightarrow \mathbb C} and {G_2 : U \rightarrow \mathbb C} be functional series with the same domain {U}. Then {G_1 \pm G_2} and {G_1 \cdot G_2} are defined pointwise.

If {G : U \rightarrow \mathbb C} is a functional series (hence holomorphic), then {G'} is defined poinwise.

If {G} is nonvanishing on {U}, then {1/G : U \rightarrow \mathbb C} is defined pointwise (and otherwise is not defined).

Now, for these finite operations, everything works as you expect:

Theorem 8 (Compatibility of finite operations)

Suppose {F}, {F_1}, {F_2} are formal series, and {G}, {G_1}, {G_2} are functional series {U \rightarrow \mathbb C}. Assume {F \simeq G}, {F_1 \simeq G_1}, {F_2 \simeq G_2}.

  • {F_1 \pm F_2 \simeq G_1 \pm G_2}, {F_1 \cdot F_2 = G_1 \cdot G_2}.
  • {F' \simeq G'}.
  • If {1/G} is defined, then {1/F} is defined and {1/F \simeq 1/G}.

So far so good: as long as we’re doing finite operations. But once we step beyond that, things begin to go haywire.

4. Limits

We need to start considering limits of {(F_k)_k} and {(G_k)_k}, since we are trying to make progress towards infinite sums and products. Once we do this, things start to burn.

Definition 9

Let {F_1 = \sum_n a_n x^n} and {F_2 = \sum_n b_n x^n} be formal series, and define the difference by

\displaystyle d(F_1, F_2) = \begin{cases} 2^{-n} & a_n \neq b_n, \; n \text{ minimal} \\ 0 & F_1 = F_2. \end{cases}

This function makes {\mathbb C[[x]]} into a metric space, so we can discuss limits in this space. Actually, it is a normed vector space obtained by {\left\lVert F \right\rVert = d(F,0)} above.

Thus, {\lim_{k \rightarrow \infty} F_k = F} if each coefficient of {x^n} eventually stabilizes as {k \rightarrow \infty}. For example, as formal series we have that {(1,-1,0,0,\dots)}, {(1,0,-1,0,\dots)}, {(1,0,0,-1,\dots)} converges to {1 = (1,0,0,0\dots)}, which we write as

\displaystyle \lim_{k \rightarrow \infty} (1 - x^k) = 1 \qquad \text{as formal series}.

As for functional series, since they are functions on the same open set {U}, we can use pointwise convergence or the stronger uniform convergence; we’ll say explicitly which one we’re doing.

Example 10 (Limits don’t work at all)

In what follows, {F_k \simeq G_k} for every {k}.

  • Here is an example showing that if {\lim_k F_k = F}, the functions {G_k} may not converge even pointwise. Indeed, just take {F_k = 1 - x^k} as before, and let {U = \{ z : |z| < 2 \}}.
  • Here is an example showing that even if {G_k \rightarrow G} uniformly, {\lim_k F_k} may not exist. Take {G_k = 1 - 1/k} as constant functions. Then {G_k \rightarrow 1}, but {\lim_k F_k} doesn’t exist because the constant term never stabilizes (in the combinatorial sense).
  • The following example from this math.SE answer by Robert Israel shows that it’s possible that {F = \lim_k F_k} exists, and {G_k \rightarrow G} pointwise, and still {F \not\simeq G}. Let {U} be the open unit disk, and set

    \displaystyle \begin{aligned} A_k &= \{z = r e^{i\theta} \mid 2/k \le r \le 1, \; 0 \le \theta \le 2\pi - 1/k\} \\ B_k &= \left\{ |z| \le 1/k \right\} \end{aligned}

    for {k \ge 1}. By Runge theorem there’s a polynomial {p_k(z)} such that

    \displaystyle |p_k(z) - 1/z^{k}| < 1/k \text{ on } A_k \qquad \text{and} \qquad |p_k(z)| < 1/k \text{ on }B_k.

    Then

    \displaystyle G_k(z) = z^{k+1} p_k(z)

    is the desired counterexample (with {F_k} being the sequence of coefficients from {G}). Indeed by construction {\lim_k F_k = 0}, since {\left\lVert F_k \right\rVert \le 2^{-k}} for each {k}. Alas, {|g_k(z) - z| \le 2/k} for {z \in A_k \cup B_k}, so {G_k \rightarrow z} converges pointwise to the identity function.

To be fair, we do have the following saving grace:

Theorem 11 (Uniform convergence and both limits exist is sufficient)

Suppose that {G_k \rightarrow G} converges uniformly. Then if {F_k \simeq G_k} for every {k}, and {\lim_k F_k = F}, then {F \simeq G}.

Proof: Here is a proof, copied from this math.SE answer by Joey Zhou. WLOG {G = 0}, and let {g_n(z) = \sum{a^{(n)}_kz^k}}. It suffices to show that {a_k = 0} for all {k}. Choose any {0<r<1}. By Cauchy’s integral formula, we have

\displaystyle \begin{aligned} \left|a_k - a^{(n)}_k\right| &= \left|\frac{1}{2\pi i} \int\limits_{|z|=r}{\frac{g(z)-g_n(z)}{z^{n+1}}\text{ d}z}\right| \\ & \le\frac{1}{2\pi}(2\pi r)\frac{1}{r^{n+1}}\max\limits_{|z|=r}{|g(z)-g_n(z)|} \xrightarrow{n\rightarrow\infty} 0 \end{aligned}

since {g_n} converges uniformly to {g} on {U}. Hence, {a_k = \lim\limits_{n\rightarrow\infty}{a^{(n)}_k}}. Since {a^{(n)}_k = 0} for {n\ge k}, the result follows. \Box

The take-away from this section is that limits are relatively poorly behaved.

5. Infinite sums and products

Naturally, infinite sums and products are defined by taking the limit of partial sums and limits. The following example (from math.SE again) shows the nuances of this behavior.

Example 12 (On {e^{1+x}})

The expression

\displaystyle \sum_{n=0}^\infty \frac{(1+x)^n}{n!} = \lim_{N \rightarrow \infty} \sum_{n=0}^N \frac{(1+x)^n}{n!}

does not make sense as a formal series: we observe that for every {N} the constant term of the partial sum changes.

But this does converge (uniformly, even) to a functional series on {U = \mathbb C}, namely to {e^{1+x}}.

Exercise 13

Let {(F_k)_{k \ge 1}} be formal series.

  • Show that an infinite sum {\sum_{k=1}^\infty F_k(x)} converges as formal series exactly when {\lim_k \left\lVert F_k \right\rVert = 0}.
  • Assume for convenience {F_k(0) = 1} for each {k}. Show that an infinite product {\prod_{k=0}^{\infty} (1+F_k)} converges as formal series exactly when {\lim_k \left\lVert F_k-1 \right\rVert = 0}.

Now the upshot is that one example of a convergent formal sum is the expression {\lim_{N} \sum_{n=0}^N a_nx^n} itself! This means we can use standard “radius of convergence” arguments to transfer a formal series into functional one.

Theorem 14 (Constructing {G} from {F})

Let {F = \sum a_nx^n} be a formal series and let

\displaystyle r = \frac{1}{\limsup_n \sqrt[n]{|c_n|}}.

If {r > 0} then there exists a functional series {G} on {U = \{ |z| < r \}} such that {F \simeq G}.

Proof: Let {F_k} and {G_k} be the corresponding partial sums of {c_0x^0} to {c_kx^k}. Then by Cauchy-Hadamard theorem, we have {G_k \rightarrow G} uniformly on (compact subsets of) {U}. Also, {\lim_k F_k = F} by construction. \Box

This works less well with products: for example we have

\displaystyle 1 \equiv (1-x) \prod_{j \ge 0} (1+x^{2^j})

as formal series, but we can’t “plug in {x=1}”, for example,

6. Finishing the original problem

We finally return to the original problem: we wish to show that the equality

\displaystyle P(x) = \prod_{j=1}^\infty (1 - x^{s_j})

cannot hold as formal series. We know that tacitly, this just means

\displaystyle \lim_{N \rightarrow \infty} \prod_{j=1}^N\left( 1 - x^{s_j} \right) = P(x)

as formal series.

Here is a solution obtained only by only considering coefficients, presented by Qiaochu Yuan from this MathOverflow question.

Both sides have constant coefficient {1}, so we may invert them; thus it suffices to show we cannot have

\displaystyle \frac{1}{P(x)} = \frac{1}{\prod_{j=1}^{\infty} (1 - x^{s_j})}

as formal power series.

The coefficients on the LHS have asymptotic growth a polynomial times an exponential.

On the other hand, the coefficients of the RHS can be shown to have growth both strictly larger than any polynomial (by truncating the product) and strictly smaller than any exponential (by comparing to the growth rate in the case where {s_j = j}, which gives the partition function {p(n)} mentioned before). So the two rates of growth can’t match.

New algebra handouts on my website

For olympiad students: I have now published some new algebra handouts. They are:

  • Introduction to Functional Equations, which cover the basic techniques and theory for FE’s typically appearing on olympiads like USA(J)MO.
  • Monsters, an advanced handout which covers functional equations that have pathological solutions. It covers in detail the solutions to Cauchy functional equation.
  • Summation, which is a compilation of various types of olympiad-style sums like generating functions and multiplicative number theory.

I have also uploaded:

  • English, notes on proof-writing that I used at the 2016 MOP (Mathematical Olympiad Summer Program).

You can download all these (and other handouts) from my MIT website. Enjoy!

Against the “Research vs. Olympiads” Mantra

There’s a Mantra that you often hear in math contest discussions: “math olympiads are very different from math research”. (For known instances, see O’Neil, Tao, and more. More neutral stances: Monks, Xu.)

It’s true. And I wish people would stop saying it.

Every time I’ve heard the Mantra, it set off a little red siren in my head: something felt wrong. And I could never figure out quite why until last July. There was some (silly) forum discussion about how Allen Liu had done extraordinarily on math contests over the past year. Then someone says:

A: Darn, what math problem can he not do?!

B: I’ll go out on a limb and say that the answer to this is “most of the problems worth asking.” We’ll see where this stands in two years, at which point the answer will almost certainly change, but research \neq Olympiads.

Then it hit me.

Ping-pong vs. Tennis

Let’s try the following thought experiment. Consider a world-class ping-pong player, call her Sarah. She has a fan-base talking about her pr0 ping-pong skills. Then someone comes along as says:

Well, table tennis isn’t the same as tennis.

To which I and everyone else reasonable would say, “uh, so what?”. It’s true, but totally irrelevant; ping-pong and tennis are just not related. Maybe Sarah will be better than average at tennis, but there’s no reason to expect her to be world-class in that too.

And yet we say exactly the same thing for olympiads versus research. Someone wins the IMO, out pops the Mantra. Even if the Mantra is true when taken literally, it’s implicitly sending the message there’s something wrong with being good at contests and not good at research.

So now I ask: just what is wrong with that? To answer this question, I first need to answer: “what is math?”.

There’s been a trick played with this debate, and you can’t see it unless you taboo the word “math”. The word “math” can refer to a bunch of things, like:

  • Training for contest problems like USAMO/IMO, or
  • Learning undergraduate/graduate materials like algebra and analysis, or
  • Working on open problems and conjectures (“research”).

So here’s the trick. The research community managed to claim the name “math”, leaving only “math contests” for the olympiad community. Now the sentence

“Math contests should be relevant to math”

seems totally innocuous. But taboo the world “math”, and you get

“Olympiads should be relevant to research”

and then you notice something’s wrong. In other words, since “math” is a substring of “math contests”, it suddenly seems like the olympiads are subordinate to research. All because of an accident in naming.

Since when? Everyone agrees that olympiads and research are different things, but it does not then follow that “olympiads are useless”. Even if ping-pong is called “table tennis”, that doesn’t mean the top ping-pong players are somehow inferior to top tennis players. (And the scary thing is that in a world without the name “ping-pong”, I can imagine some people actually thinking so.)

I think for many students, olympiads do a lot of good, independent of any value to future math research. Math olympiads give high school students something interesting to work on, and even the training process for a contest such that the IMO carries valuable life lessons: it teaches you how to work hard even in the face of possible failure, and what it’s like to be competitive at an international level (i.e. what it’s like to become really good at something after years of hard work). The peer group that math contests give is also wonderful, and quite similar to the kind of people you’d meet at a top-tier university (and in some cases, they’re more or less the same people). And the problem solving ability you gain from math contests is indisputably helpful elsewhere in life. Consequently, I’m well on record as saying the biggest benefits of math contests have nothing to do with math.

There are also more mundane (but valid) reasons (they help get students out of the classroom, and other standard blurbs about STEM and so on). And as a matter of taste I also think contest problems are interesting and beautiful in their own right. You could even try to make more direct comparisons (for example, I’d guess the average arXiv paper in algebraic geometry gets less attention than the average IMO geometry problem), but that’s a point for another blog post entirely.

The Right and Virtuous Path

Which now leads me to what I think is a culture issue.

MOP alumni prior to maybe 2010 or so were classified into two groups. They would either go on to math research, which was somehow seen as the “right and virtuous path“, or they would defect to software/finance/applied math/etc. Somehow there is always this implicit, unspoken message that the smart MOPpers do math research and the dumb MOPpers drop out.

I’ll tell you how I realized why I didn’t like the Mantra: it’s because the only time I hear the Mantra is when someone is belittling olympiad medalists.

The Mantra says that the USA winning the IMO is no big deal. The Mantra says Allen Liu isn’t part of the “smart club” until he succeeds in research too. The Mantra says that the countless time and energy put into running each year’s MOP are a waste of time. The Mantra says that the students who eventually drop out of math research are “not actually good at math” and “just good at taking tests”. The Mantra even tells outsiders that they, too, can be great researchers, because olympiads are useless anyways.

The Mantra is math research’s recruiting slogan.

And I think this is harmful. The purpose of olympiads was never to produce more math researchers. If it’s really the case that olympiads and research are totally different, then we should expect relatively few olympiad students to go into research; yet in practice, a lot of them do. I think one could make a case that a lot of the past olympiad students are going into math research without realizing that they’re getting into something totally unrelated, just because the sign at the door said “math”. One could also make a case that it’s very harmful for those that don’t do research, or try research and then decide they don’t like it: suddenly these students don’t think they’re “good at math” any more, they’re not smart enough be a mathematician, etc.

But we need this kind of problem-solving skill and talent too much for it to all be spent on computing R(6,6). Richard Rusczyk’s take from Math Prize for Girls 2014 is:

When people ask me, am I disappointed when my students don’t go off and be mathematicians, my answer is I’d be very disappointed if they all did. We need people who can think about these complex problems and solve really hard problems they haven’t seen before everywhere. It’s not just in math, it’s not just in the sciences, it’s not just in medicine — I mean, what we’d give to get some of them in Congress!

Academia is a fine career, but there’s tons of other options out there: the research community may denounce those who switch out as failures, but I’m sure society will take them with open arms.

To close, I really like this (sarcastic) comment from Steven Karp (near bottom):

Contest math is inaccessible to over 90% of people as it is, and then we’re supposed to tell those that get it that even that isn’t real math? While we’re at it, let’s tell Vi Hart to stop making videos because they don’t accurately represent math research.

Addendums (response to comments)

Thanks first of all for the many long and thoughtful comments from everyone (both here, on Facebook, in private, and so on). It’s given me a lot to think about.

Here’s my responses to some of the points that were raised, which is necessarily incomplete because of the volume of discussion.

  1. To start off, it was suggested I should explicitly clarify: I do not mean to imply that people who didn’t do well on contests cannot do well in math research. So let me say that now.

  2. My favorite comment that I got was that in fact this whole post pattern matches with bravery debates.

    On one hand you have lots of olympiad students who actually FEEL BAD about winning medals because they “weren’t doing real math”. But on the other hand there are students whose parents tell them to not pursue math as a major or career because of low contest scores. These students (and their parents) would benefit a lot from the Mantra; so I concede that there are indeed good use cases of the Mantra (such as those that Anonymous Chicken, betaveros describe below) and in particular the Mantra is not intrinsically bad.

    Which of these use is the “common use” probably depends on which tribes you are part of (guess which one I see more?). It’s interesting in that in this case, the two sides actually agree on the basic fact (that contests and research are not so correlated).

  3. Some people point out that research is a career while contests aren’t. I am not convinced by this; I don’t think “is a career” is a good metric for measuring value to society, and can think of several examples of actual jobs that I think really should not exist (not saying any names). In addition, I think that if the general public understood what mathematicians actually do for a career, they just might be a little less willing to pay us.

    I think there’s an interesting discussion about whether contests / research are “valuable” or not, but I don’t think the answer is one-sided; this would warrant a whole different debate (and would derail the entire post if I tried to address it).

  4. Some people point out that training for olympiads yields diminishing returns (e.g. learning Muirhead and Schur is probably not useful for anything else). I guess this is true, but isn’t it true of almost anything? Maybe the point is supposed to be “olympiads aren’t everything”, which is agreeable (see below).

  5. The other favorite comment I got was from Another Chicken, who points out below that the olympiad tribe itself is elitist: they tend to wall themselves off from outsiders (I certainly do this), and undervalue anything that isn’t hard technical problems.

    I concede these are real problems with the olympiad community. Again, this could be a whole different blog post.

    But I think this comment missed the point of this post. It is probably fine (albeit patronizing) to encourage olympiad students to expand; but I have a big problem with framing it as “spend time on not-contests because research“. That’s the real issue with the Mantra: it is often used as a recruitment slogan, telling students that research is the next true test after the IMO has been conquered.

    Changing the Golden Metric from olympiads to research seems to just make the world more egotistic than it already is.

Against Hook-Length on USAMO 2016/2

A recent USAMO problem asked the contestant to prove that

\displaystyle  (k^2)! \cdot \prod_{j=0}^{k-1} \frac{j!}{(j+k)!}

is an integer for every {k \in \mathbb N}. Unfortunately, it appears that this is a special case of the so-called hook-length formula, applied to a {k \times k} Young tableau, and several students appealed to this fact without proof to produce one-line solutions lacking any substance. This has led to a major controversy about how such solutions should be graded, in particular whether they should receive the {7^-} treatment for “essentially correct solutions”, or the {0^+} treatment for “essentially not solved”.

In this post I want to argue that I think that these solutions deserve a score of {1}.

1. Disclaimers

However, before I do so, I would like to make some disclaimers:

  • This issue is apparently extremely polarized: everyone seems to strongly believe one side or the other.
  • This was an extremely poor choice of a USAMO problem, and so there is no “good” way to grade the HL solutions, only a least bad way. The correct solution to the dilemma is to not have used the problem at all. Yet here’s the bloodied patient, and here we are in the emergency room.
  • While I am a grader for the USAMO, I am one of many graders, and what I say in this post does not necessarily reflect the viewpoints of other USAMO graders or what score the problem will actually receive. In other words, this is my own view and not official in any way.

One last remark is that I do not consider the hook-length formula to be a “well-known” result like so many contestants seem to want to pretend it is. However, this results in the danger of what constitutes “well-known” or not. So in what follows I’ll pretend that the HL formula is about as well-known as, say, the Pascal or Zsigmondy theorem, even though I personally don’t think that this is the case.

One final disclaimer: I am unlikely to respond to further comments about an issue this polarized, since I have already spent many hours doing so, and I’ve done enough of my duty. So if I don’t respond to a comment of yours, please don’t take it personally.

2. Rule for citations

Here is the policy I use for citations when grading:

  • You can cite any named result as long as it does not trivialize the problem.
  • If the result trivializes the problem, then you are required to prove the result (or otherwise demonstrate you understand the proof) in order to use it.

This is what I’ve heard every time I have asked or answered this question; I have never heard anything to the contrary.

Some people apparently want to nit-pick about how “trivialize” is not objective. I think this is silly. If you really want a definition of “trivialize”, you can take “equivalent to the problem or a generalization of the problem” as a rule of thumb.

Clearly it follows from my rule above that the hook-length formula deserves {0^+} grading, so the remainder of the post is dedicated to justifying why I think this is the correct rule.

3. Subjective grading

I would rather have an accurate subjective criteria than a poor objective one.

In an ideal world, grading would be completely objective: a solution which solves the problem earns {7^-} points and a solution which does not solve the problem earns {0^+} points. But in practice this is of course not possible, unless we expect our contestants to write their solutions in a formal language like Coq. Since this is totally infeasible, we instead use informal proofs: students write their solutions in English and human graders assign a score based on whether the solution could in principle be compiled into a formal language proof.

What this means is that in grading, there are subjective decisions made all of the time. A good example of this is omitting steps. Suppose a student writes “case {B} is similar [to case {A}]”. Then the grader has to decide whether or not the student actually knows that the other case is similar or not, or is just bluffing. One one extreme, if {A} and {B} really are identical, then the grader would probably accept the claim. On the other extreme, if {A} and {B} have some substantial differences, then the grader would almost certainly reject the claim. This implies that there is some intermediate “gray area” which cannot be objectively defined.

Fortunately, most of these decisions are clear, thus USAMO grading appears externally to be mostly objective. In other words, accurate grading and objective grading are correlated (yay math!), but they are not exactly the same. All scores are ultimately discretion by human graders, and not some set of rigid guidelines.

Citations are a special case of this. By citing a theorem, a student is taking advantage of convention that a well-known proof to both the student and grader can be omitted from the write-up.

4. Citing the problem

In light of this I don’t think you should get points for citing the problem. I think we all agree that if a student writes “this is a special case of IMO Shortlist 1999 G8”, they shouldn’t get very many points.

The issue with citing HL in lieu of solving the problem is that the hook-length formula is very hard to prove, and it is not reasonable to do so in an olympiad setting. Consequently, it is near certain that these students have essentially zero understanding of the solution to the problem; they have not solved it, they have only named it.

Similarly, I think you should not earn points for trivializing a problem using Dirichlet, Prime Number Theorem, Zsigmondy, etc. This is also historically consistent with the way that grading has been done in the past (hi Palmer!).

5. Citing intermediate steps

Now consider the usage of difficult theorems such as Dirichlet, Prime Number Theorem, etc. on a solution in which they are merely an intermediate step rather than the entire problem. The consensus here is that citing these results is okay (though it is not unanimous; some super harsh graders also want to take off points here, but they are very few in my experience).

I think this is acceptable, because in this case the contestant has done 90% of the solution, and cannot do the remaining 10% but recognize it as well-known. In my eyes this is considered as essentially solving the problem, because the last missing bit is a standard fact. But somehow if you cannot do 100% of the problem, I don’t think that counts as solving the problem.

What I mean is there is a subjective dependence both on how much of the solution the student actually understands, and how accessible the result is. Unfortunately, the HL solutions earn the worst possible rank in both of the categories: the student understands 0% of the solution and moreover the result is completely inaccessible.

6. Common complaints

Here are the various complaints that people have made to me.

  • “HL is well-known.”
    Well, I don’t think it is, but in any case that’s not the point; you cannot cite a result which is (a) more general than the problem, and (b) to which you don’t understand the proof.

  • “Your criteria is subjective!”
    So what? I would rather have an accurate subjective criteria than a poor objective one.

  • “It’s the problem writer’s fault, so students should get {7}.”
    This is not an ethics issue. It is not appropriate to award points of sympathy on a serious contest such as the USAMO; score inflation is not going to help anyone.

  • “It’s elitist for the graders to decide what counts as trivialized.”
    That’s the grader’s job. Again I would rather have an accurate subjective criteria than a poor objective one. In practice I think the graders are very reasonable about decisions.

  • “I don’t think anyone disputes that the HL solution is a correct one, so certainly the math dictates a {7^-}.”
    I dispute it: I don’t think citing HL is a solution at all.

  • “Why do we let students use Pascal / Cauchy / etc?”
    Because these results are much more reasonable to prove, and the “one-line” solutions using Pascal and Cauchy are not completely trivial; the length of a solution is not the same thing as its difficulty. Of course this is ultimately subjective, but I would rather have an accurate subjective criteria than a poor objective one.

  • “HL solutions have substance, because we made an observation that the quantity is actually the number of ways to do something.”
    That’s why I wish to award {1} instead of {0}.

  • “Your rule isn’t written anywhere.”
    Unfortunately, none of the rules governing USAMO are written anywhere. I agree this is bad and the USAMO should publish some more clear description of the grading mechanics.

  • “The proof of the HLF isn’t even that complicated.”
    Are you joking me?

In summary, I don’t think it is appropriate to give full marks to a student who cannot solve a problem just because they can name it.

Stop Paying Me Per Hour

Occasionally I am approached by parents who ask me if I am available to teach their child in olympiad math. This is flattering enough that I’ve even said yes a few times, but I’m always confused why the question is “can you tutor my child?” instead of “do you think tutoring would help, and if so, can you tutor my child?”.

Here are my thoughts on the latter question.

Charging by Salt

I’m going to start by clearing up the big misconception which inspired the title of this post.

The way tutoring works is very roughly like the following: I meet with the student once every week, with custom-made materials. Then I give them some practice problems to work on (“homework”), which I also grade. I throw in some mock olympiads. I strongly encourage my students to email me with questions as they come up. Rinse and repeat.

The actual logistics vary; for example, for small in-person groups I prefer to do every other week for 3 hours. But the thing that never changes is how the parents pay me. It’s always the same: I get N \gg 0 dollars per hour for the actual in-person meeting, and 0 dollars per hour for preparing materials, grading homework, responding to questions, and writing the mock olympiads.

Now I’m not complaining because N is embarrassingly large. But one day I realized that this pricing system is giving parents the wrong impression. They now think the bulk of the work is from me taking the time to meet with their child, and that the homework is to help reinforce what I talk about in class. After all, this is what high school does, right?

I’m here to tell you that this is completely wrong.

It’s the other way around: the class is meant to supplement the homework. Think salt: for most dishes you can’t get away with having zero salt, but you still don’t price a dish based on how much salt is in it. Similarly, you can’t excise the in-person meeting altogether, but the dirty secret is that the classtime isn’t the core component.

I mean, here’s the thing.

  • When you take the IMO, you are alone with a sheet of paper that says “Problem 1”, “Problem 2”, “Problem 3”.
  • When you do my homework, you are alone with a sheet of paper that says “Problem 1”, “Problem 2”, “Problem 3”.
  • When you’re in my class, you get to see my beautiful smiling face plus a sheet of paper that says “Theorem 1”, “Example 2”, “Example 3”.

Which of these is not like the other?

Active Ingredients

So we’ve established that the main active ingredient is actually you working on problems alone in your room. If so, why do you need a teacher at all?

The answer depends on what the word “need” means. No USA IMO contestant in my recent memory has had a coach, so you don’t need a coach. But there are some good reasons why one might be helpful.

Some obvious reasons are social:

  • Forces you to work regularly; though most top students don’t really have a problem with self-motivation
  • You have a person to talk to. This can be nice if you are relatively isolated from the rest of the math community (e.g. due to geography).
  • You have someone who will answer your questions. (I can’t tell you how jealous I am right now.)
  • Feedback on solutions to problems. This includes student’s written solutions (stylistic remarks, or things like “this lemma you proved in your solution is actually just a special case of X” and so on) as well as explaining solutions to problems the student fails to solve.

In short, it’s much more engaging to study math with a real person.

Those reasons don’t depend so much on the instructor’s actual ability. Here are some reasons which do:

  • Guidance. An instructor can tell you what things to learn or work on based on their own experience in the past, and can often point you to things that you didn’t know existed.
  • It’s a big plus if the instructor has a good taste in problems. Some problems are bad and don’t teach you anything; some (old) problems don’t resemble the flavor of problems that actually appear on olympiads. On the flip side, some problems are very instructive or very pretty, and it’s great if your teacher knows what these are.
  • Ideally, also a good taste in topics. For example, I strongly object to classes titled “collinearity and concurrence” because this may as well be called “geometry”, and I think that such global classes are too broad to do anything useful. Conversely, examples of topics I think should be classes but aren’t: “looking at equality cases”, “explicit constructions”, “Hall’s marriage theorem”, “greedy algorithms”. I make this point a lot more explicitly in Section 2 of this blog post of mine.

In short, you’re also paying for the material and expertise. Past IMO medalists know how the contest scene works. Parents and (beginning) students less so.

Lastly, the reason which I personally think is most important:

  • Conveys strong intuition/heuristics, both globally and for specific problems. It’s hard to give concrete examples of this, but a few global ones I know were particularly helpful for me: “look at maximal things” (Po-Shen Loh on greedy algorithms), “DURR WE WANT STUFF TO CANCEL” (David Yang on FE’s), “use obvious inequalities” (Gabriel Dospinescu on analytic NT), which are take-aways that have gotten me a lot of points. This is also my biggest criteria for evaluating my own written exposition.

You guys know this feeling, I’m sure: when your English teacher assigned you an passage to read, the fastest way to understand it is to not read the passage but to ask the person sitting next to you what it’s saying. I think this is in part because most people are awful at writing and don’t even know how to write for other human beings.

The situation in olympiads is the same. I estimate listening to me explain a solution is maybe 4 to 10 times faster than reading the official solution. Turns out that writing up official solutions for contests is a huge chore, so most people just throw a sequence of steps at the reader without even bothering to identify the main ideas. (As a contest organizer, I’m certainly guilty of this laziness too!)

Aside: I think this is a large part of why my olympiad handouts and other writings have been so well-received. Disclaimer: this was supposed to be a list of what makes a good instructor, but due to narcissism it ended up being a list of things I focus on when teaching.

Caveat Emptor

And now I explain why the top IMO candidates still got by without teachers.

It turns out that the amount of math preparation time that students put in doesn’t seem to be a normal distribution. It’s a log normal distribution. And the reason is this: it’s hard to do a really good job on anything you don’t think about in the shower.

Officially, when I was a contestant I spent maybe 20 hours a week doing math contest preparation. But the actual amount of time is higher. The reason is that I would think about math contests more like 24/7. During English class, I would often be daydreaming about the inequality I worked on last night. On the car ride home, I would idly think about what I was going to teach my middle school students the next week. To say nothing of showers: during my showers I would draw geometry diagrams on the wall with water on my finger.

So spiritually, I maybe spent 10 times as much time on math olympiads compared to an average USA(J)MO qualifier.

And that factor of 10 is enormous. Even if I as a coach can cause you to learn two or three or four times more efficiently, you will still lose to that factor of 10. I’d guess my actual multiplier is somewhere between 2 and 3, so there you go. (Edit: this used to say 3 to 4, I think that’s too high now.)

The best I can do is hope that, in addition to making my student’s training more efficient, I also cause my students to like math more.

Some Advice for Olympiad Geometry

I know some friends who are fantastic at synthetic geometry. I can give them any problem and they’ll come up with an incredibly impressive synthetic solution. I also have some friends who are very bad at synthetic geometry, but have such good fortitude at computations that they can get away with using Cartesian coordinates for everything.

I don’t consider myself either of these types; I don’t have much ingenuity when it comes to my solutions, and I’m actually quite clumsy when it comes to long calculations. But nonetheless I have a high success rate with olympiad geometry problems. Not only that, but my solutions are often very algorithmic, in the sense that any well-trained student should be able to come up with this solution.

In this article I try to describe how I come up which such solutions.

1. The Three Reductions

Very roughly, there are three different ways I try to make progress on a geometry problem.

  • (I) The standard synthetic techniques; angle chasing, cyclic quadrilaterals, homothety, radical axis / power of a point, etc. My own personal arsenal contains some weapons not known to many contestants as well, most notably inversion, harmonic bundles and quadrilaterals, and spiral similarity / Miquel points.For this part, it’s highly advantageous to be well-versed with “standard” configurations and tricks. To give an extreme example: to solve Iran TST 2009, Problem 9 one essentially needs only recognize two configurations: a lemma about the midpoint of an altitude (2002 G7) and another lemma about the line {EF} (USAJMO 2014/6). Not knowing either of these makes it more difficult to solve the problem synthetically in the time limit. As a reference, Yufei Zhao’s lemmas handout contains a fairly comprehensive list of these configurations.

    Easier problems don’t require as much in this way of configuration recognition.

  • (II) Standard computational techniques (aka bashing). Personally, I prefer complex numbers and barycentric coordinates but I know other students who will use Cartesian coordinates and trigonometry to great success. The advantage of such methods is that they are straightforward and reliable, albeit tedious and time-consuming. It is mostly a matter of experience to understand whether a calculation can be carried out within the time limit — I can basically tell just by looking at a setup whether it can be solved in this time.
  • (III) Most surprisingly: simply finding crucial claims. Especially for harder problems like IMO 3/6 much of the time the key to solving a problem is making some key observation. Said another way: a difficult IMO 3/6 problem which asks you to prove {A \implies B} might have a solution which goes like,

    \displaystyle A \implies X \implies Y \implies B.

    Each of the individual implications might be no harder than an IMO 1/4 but the difficulty rests in finding what to prove. The most reliable way to do such things is to draw large, in-scale diagrams. If you are good at recognizing cyclic quadrilaterals, collinear points, etc. then the correct claims will naturally suggest themselves; conversely, good diagrams will prevent you from wasting time trying to prove things that aren’t true (effectively letting you test your claims “experimentally” before trying to prove them).

Type (III) deserves some comment here. There is more to making progress on a problem than simply trying things you think will solve the problem: there is some “scouting” involved that you will need to do for any difficult problems. As a terrible analogy, in StarCraft you have to scout an experienced opponent to understand what they’re doing before you try to attack them. The situation with IMO 3/6 is no different: you have to have some understanding of the problem before you stand a chance of being able to solve it.

Easy problems can often succumb to just one class of attacks, but the interesting and difficult problems can require two or all three classes in order to solve. How much you use each type of strategy is in my opinion a matter of personal taste — some people don’t use (II) at all and rely on (I) to prove everything, and even vice versa! I like to think I balance (I) and (II) evenly. But (III) is indispensable, and in any case I think part of the reason I have been so successful with geometry problems is precisely that I can draw on all three strategies in tandem, rather than being limited to one or two.

In fact, a good rule of thumb that I use for judging the difficulty of a problem is how many of the above methods I had to use: the {n}th problem on an IMO paper should require me to resort to about {n} of these strategies.

2. Concrete Examples

I’ll now give some concrete examples of the things I said above. Warning: spoilers follow, and hyperlinks lead to my solutions on Art of Problem Solving. You are encouraged to try the problems yourself before reading the comments.

Example [EGMO 2012/1] Let {ABC} be a triangle with circumcenter {O}. The points {D}, {E}, {F} lie in the interiors of the sides {BC}, {CA}, {AB} respectively, such that {\overline{DE}} is perpendicular to {\overline{CO}} and {\overline{DF}} is perpendicular to {\overline{BO}}. Let {K} be the circumcenter of triangle {AFE}. Prove that the lines {\overline{DK}} and {\overline{BC}} are perpendicular.

This is a pretty typical entry-level geometry problem. Do some angle chasing (I) to find one cyclic quad (III), and then follow through to solve the problem (I). If you are good enough, you don’t even need to find the cyclic quad in advance; just play around with the angles until you notice it.

Example [IMO 2014, Problem 4] Let {P} and {Q} be on segment {BC} of an acute triangle {ABC} such that {\angle PAB=\angle BCA} and {\angle CAQ=\angle ABC}. Let {M} and {N} be the points on {AP} and {AQ}, respectively, such that {P} is the midpoint of {AM} and {Q} is the midpoint of {AN}. Prove that the intersection of {BM} and {CN} is on the circumference of triangle {ABC}.

You can solve this problem by barycentric coordinates (II) instantly (textbook example). Also similar triangles (I) solves the problem pretty quickly as well. Again, this problem is “easy” in the sense that one can directly approach it with either (I) or (II), not needing (III) at all.

Example [USAMO 2015/2] Quadrilateral {APBQ} is inscribed in circle {\omega} with {\angle P = \angle Q = 90^{\circ}} and {AP = AQ < BP}. Let {X} be a variable point on segment {\overline{PQ}}. Line {AX} meets {\omega} again at {S} (other than {A}). Point {T} lies on arc {AQB} of {\omega} such that {\overline{XT}} is perpendicular to {\overline{AX}}. Let {M} denote the midpoint of chord {\overline{ST}}. As {X} varies on segment {\overline{PQ}}, show that {M} moves along a circle.

This was not supposed to be a very difficult problem, but it seems to have nearly swept the JMO group. Essentially, the key to this problem is to notice that the center of the desired circle is in fact the midpoint of {AO} (with {O} the center of the circle). This is a huge example of (III) — after this observation, one can solve the problem very quickly using complex numbers (II). It is much harder (though not impossible) to solve the problem without knowing the desired center.

Example [USAMO 2014/5] Let {ABC} be a triangle with orthocenter {H} and let {P} be the second intersection of the circumcircle of triangle {AHC} with the internal bisector of the angle {\angle BAC}. Let {X} be the circumcenter of triangle {APB} and {Y} the orthocenter of triangle {APC}. Prove that the length of segment {XY} is equal to the circumradius of triangle {ABC}.

Personally I think the most straightforward solution is to use (I) to eliminate the orthocenter condition, and then finish with complex numbers (II). Normally, you won’t see a medium-level problem that dies immediately to (II), and the only reason a problem like this could end up as a problem 5 is that there is a tiny bit of (I) that needs to happen before the complex numbers becomes feasible.

Example [IMO 2014/3] Convex quadrilateral {ABCD} has {\angle ABC = \angle CDA = 90^{\circ}}. Point {H} is the foot of the perpendicular from {A} to {BD}. Points {S} and {T} lie on sides {AB} and {AD}, respectively, such that {H} lies inside triangle {SCT} and

\displaystyle \angle CHS - \angle CSB = 90^{\circ}, \quad \angle THC - \angle DTC = 90^{\circ}.

Prove that line {BD} is tangent to the circumcircle of triangle {TSH}.

Like most IMO 3/6’s I had to resort to using all three methods in order to solve this problem. The first important step was finding out what to do with the angle condition. It turns out that in fact, it’s equivalent to the circumcenter of triangle {TCH} lying on side {AD} of the triangle (III); proving this is then a matter of angle chasing (I). Afterwards, one has to recognize a tricky usage of the angle bisector theorem (I) to reduce it to something that can be computed with trigonometry (II). This leads to a direct solution that, while not elegant, also requires much less ingenuity then most of the solutions found by friends I know.

I really want to stress that being proficient in all three strategies is key to getting “straightforward” solutions like this to IMO 3/6 caliber problems. If you miss any of these components, you are not going to solve the problem.

Example [IMO 2011/6] Let {ABC} be an acute triangle with circumcircle {\Gamma}. Let {\ell} be a tangent line to {\Gamma}, and let {\ell_a}, {\ell_b}, {\ell_c} be the lines obtained by reflecting {\ell} in the lines {BC}, {CA}, and {AB}, respectively. Show that the circumcircle of the triangle determined by the lines {\ell_a}, {\ell_b}, and {\ell_c} is tangent to the circle {\Gamma}.

The ultimate example of these three principles. Using a trick that showed up on APMO 2014/5 and RMM 2013/3, one constructs the tangency point {T} and connects the points {A_1}, {B_1}, {C_1}, as I explain in this post, yielding points {A_2}, {B_2}, {C_2}. After that, a very careful examination of the diagram (possibly several diagrams) leads to a conjecture that {A_1A=AP}, et cetera. This is the key observation (III), and leads to highly direct solution via (II). But the point of this problem is that you need to have the guts to construct those auxiliary points and then boldly claim they are the desired “squared” points.

3. Comparison with Other Subjects

The approaches I’ve described highlight some of the features of olympiad geometry which distinguish it from other subjects.

  • Unlike other olympiad subjects, you can actually obtain a big advantage by just knowing lots of theory. Experienced contestants simply “recognize” a large body of common configurations that those without access to training materials have never seen before. Similarly, there are a lot of fancy techniques that can make a big difference. This is much less true of other subjects (for example combinatorics is the opposite extreme).
  • There’s less variance in the subject: lots of Euclidean geometry problems feel the same, and all of them use the same body of techniques. It reminds me of chess: it’s very “narrow” in the sense that at the end of the day, there are only so many possible moves. (Olympiad inequalities also has this kind of behavior.) Again combinatorics is the opposite of this.
  • You have a reliable backup in case you can’t find the official solution: bash. Moreover, in general there are often many different ways to solve a problem; not true of other subjects.
  • If you want to make some “critical claim” you can quickly test it empirically (by drawing a good diagram).

 

Writing Olympiad Geometry Problems

You can use a wide range of wild, cultivated or supermarket greens in this recipe. Consider nettles, beet tops, turnip tops, spinach, or watercress in place of chard. The combination is also up to you so choose the ones you like most.

— Y. Ottolenghi. Plenty More

In this post I’ll describe how I come up with geometry proposals for olympiad-style contests. In particular, I’ll go into detail about how I created the following two problems, which were the first olympiad problems which I got onto a contest. Note that I don’t claim this is the only way to write such problems, it just happens to be the approach I use, and has consistently gotten me reasonably good results.

[USA December TST for 56th IMO] Let {ABC} be a triangle with incenter {I} whose incircle is tangent to {\overline{BC}}, {\overline{CA}}, {\overline{AB}} at {D}, {E}, {F}, respectively. Denote by {M} the midpoint of {\overline{BC}} and let {P} be a point in the interior of {\triangle ABC} so that {MD = MP} and {\angle PAB = \angle PAC}. Let {Q} be a point on the incircle such that {\angle AQD = 90^{\circ}}. Prove that either {\angle PQE = 90^{\circ}} or {\angle PQF = 90^{\circ}}.

DecTST-statement

[Taiwan TST Quiz for 56th IMO] In scalene triangle {ABC} with incenter {I}, the incircle is tangent to sides {CA} and {AB} at points {E} and {F}. The tangents to the circumcircle of {\triangle AEF} at {E} and {F} meet at {S}. Lines {EF} and {BC} intersect at {T}. Prove that the circle with diameter {ST} is orthogonal to the nine-point circle of {\triangle BIC}.

TWTST-statement

1. General Procedure

Here are the main ingredients you’ll need.

  • The ability to consistently solve medium to hard olympiad geometry problems. The intuition you have from being a contestant proves valuable when you go about looking for things.
  • In particular, a good eye: in an accurate diagram, you should be able to notice if three points look collinear or if four points are concyclic, and so on. Fortunately, this is something you’ll hopefully have just from having done enough olympiad problems.
  • Geogebra, or some other software that will let you quickly draw and edit diagrams.

With that in mind, here’s the gist of what you do.

  1. Start with a configuration of your choice; something that has a bit of nontrivial structure in it, and add something more to it. For example, you might draw a triangle with its incircle and then add in the excircle tangency point, and the circle centered at {BC} passing through both points (taking advantage of the fact that the two tangency points are equidistant from {B} and {C}).
  2. Start playing around, adding in points and so on to see if anything interesting happens. You might be guided by some actual geometry constructions: for example, if you know that the starting configuration has a harmonic bundle in it, you might project this bundle to obtain the new points to play with.
  3. Keep going with this until you find something unexpected: three points are collinear, four points are cyclic, or so on. Perturb the diagram to make sure your conjecture looks like it’s true in all cases.
  4. Figure out why this coincidence happened. This will probably add more points to you figure, since you often need to construct more auxiliary points to prove the conjecture that you have found.
  5. Repeat the previous two steps to your satisfaction.
  6. Once you are happy with what you have, you have a nontrivial statement and probably several things that are equivalent to it. Pick the one that is most elegant (or hardest), and erase auxiliary points you added that are not needed for the problem statement.
  7. Look for other ways to reduce the number of points even further, by finding other equivalent formulations that have fewer points.

Or shorter yet: build up, then tear down.

None of this makes sense written this abstractly, so now let me walk you through the two problems I wrote.

2. The December TST Problem

In this narrative, the point names might be a little strange at first, because (to make the story follow-able) I used the point names that ended up in the final problem, rather than ones I initially gave. Please bear with me!

I began by drawing a triangle {ABC} (always a good start\dots) and its incircle, tangent to side {BC} at {D}. Then, I added in the excircle touch point {T}, and drew in the circle with diameter {DT}, which was centered at the midpoint {M}. This was a coy way of using the fact that {MD = MT}; I wanted to see whether it would give me anything interesting.

So, I now had the following picture.

DecTST-initial

Now I had two circles intersecting at a single point {D}, so I added in {Q}, the second intersection. But really, this point {Q} can be thought of another way. If we let {DS} be the diameter of the incircle, then as {DT} is the other diameter, {Q} is actually just the foot of the altitude from {D} to line {ST}.

But recall that {A}, {S}, {T} are collinear! (Again, this is why it’s helpful to be familiar with “standard” contest configurations; you see these kind of things immediately.) So {Q} in fact lies on line {AT}.

DecTST-point-q

This was pretty cool, though not yet interesting enough to be a contest problem. So I looked for most things that might be true.

I don’t remember what I tried next; it didn’t do anything interesting. But I do remember the thing I tried after that: I drew in the angle bisector, line {AI}. And then, I noticed a big coincidence: the first intersection of {AI} with the circle with diameter {DT} seemed to lie on line {DE}! I was initially confused by this; it didn’t seem like it could possibly be true due to symmetry reasons. But in my diagram, it was indeed correct. A moment later, I realized the reason why this was plausible: in fact, the second intersection of line {AI} with the circle was on line {DF}.

DecTST-collin

Now, I could not see quickly at all why this was true. So I started trying to prove it, but initially failed: however, I managed to show (via angle chasing) that

\displaystyle D, P, E \text{ collinear} \iff \angle PQE = 90^\circ.

So, at least I had an interesting equivalent statement.

DecTST-almost-sol

After another half hour of trying to prove my conjecture, I finally realized what was happening. The point {P} was the one attached to a particular lemma: the {A}-bisector, {B}-midline, and {C} touch-chord are concurrent, and from this {MD = MP} just follows by some similar triangles. So, drawing in the point {N} (the midpoint of {AB}), I had the full configuration which gave the answer to my conjecture.

DecTST-full-sol

Finally, I had to clean up the mess that I had made. How could I do this? Well, the points {N}, {S} could be eliminated easily enough. And we could re-define {Q} to be a point on the incircle such that {\angle AQD = 90^\circ}. This actually eliminated the green circle and point {T} altogether, provided we defined {P} by just saying that it was on the angle bisector, and that {MD = MP}. (So while the circle was still implicit in the condition {MD = MP}, it was no longer explicitly part of the problem.)

Finally, we could even remove the line through {D}, {P} and {E}; we ask the contestant to prove {\angle PQE = 90^\circ}.

DecTST-statement

And that was it!

3. The Taiwan TST Problem

In fact, the starting point of this problem was the same lemma which provided the key to the previous solution: the circle with diameter {BC} intersects the {B} and {C} bisectors on the {A} touch chord. Thus, we had the following diagram.

TWTST-iran

The main idea I had was to look at the points {D}, {X}, {Y} in conjunction with each other. Specifically, this was the orthic triangle of {\triangle BIC}, a situation which I had remembered from working on Iran TST 2009, Problem 9. So, I decided to see what would happen if I drew in the nine-point circle of {\triangle BIC}. Naturally, this induces the midpoint {M} of {BC}.

TWTST-nine-point

At this point, notice (or recall!) that line {AM} is concurrent with lines {DI} and {EF}.

TWTST-median

So the nine-point circle of the problem is very tied down to the triangle {BIC}. Now, since I was in the mood for something projective, I constructed the point {T}, the intersection of lines {EF} and {BC}. In fact, what I was trying to do was take perspectivity through {I}. From this we actually deduce that {(T,K;X,Y)} is a harmonic bundle.

TWTST-add-T

Now, what could I do with this picture? I played around looking for some coincidences, but none immediately presented themselves. But I was enticed by the point {T}, which was somehow related to the cyclic complete quadrilateral {XYMD}. So, I went ahead and constructed the pole of {T} to the nine-point circle, letting it hit line {BC} at {L}. This was aimed at “completing” the picture of a cyclic quadrilateral and the pole of an intersection of two sides. In particular, {(T,L;D,M)} was harmonic too.

TWTST-almost

I spent a long time thinking about how I could make this into a problem. I unfortunately don’t remember exactly what things I tried, other than the fact that I was taking a lot of perspectivity. In particular, the “busiest” point in the picture is {K}, so it makes sense to try and take perspectives through it. Especially enticing was the harmonic bundle

\displaystyle \left( \overline{KT}, \overline{KL}; \overline{KD}, \overline{KM} \right) = -1.

How could I use this to get a nice result?

Finally about half an hour I got the right idea. We could take this bundle and intersect it with the ray {AI}! Now, letting {N} be the midpoint {EF}, we find that three of the points in the harmonic bundle we obtain are {A}, {I}, and {N}; let {S} be the fourth point, which is the intersection of line {KL} with {AI}. Then by hypothesis, we ought to have {(A,I;N,S) = -1}. But from this we know exactly what the point {S}. Just look at the circumcircle of triangle {AEF}: as this has diameter {AI}, we see that {S} is the intersection of the tangents at {E} and {F}.

TWTST-final-sol

Consequently, we know that the point {S}, defined very naturally in terms of the original picture, lies on the polar of {T} to the nine-point circle. By simply asking the contestant to prove this, we thus eliminate all the points {K}, {M}, {D}, {N}, {I}, {X}, and {Y} completely from the picture, leaving only the nine-point circle. Finally, instead of directly asking the contestant to show that {T} lies on the polar of {S}, one can rephrase the problem as saying “the circle with diameter {ST} is orthogonal to the nine-point circle of {\triangle BIC}”, concealing all the work that went into the creation of the problem.

TWTST-statement

Fantastic.