Some Thoughts on Olympiad Material Design

Posted on 8 April, 201715 November, 2017 by Evan Chen (陳誼廷)

(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:

Direct angle chasing
Power of a point / radical axis
Homothety, similar triangles, ratios
Recognizing some standard configuration (see Yufei for a list)
Doing some length calculations
Complex numbers
Barycentric coordinates
Inversion
Harmonic bundles or pole/polar and homography
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.

Published by Evan Chen (陳誼廷)

I am a math olympiad coach and a PhD student at MIT. View all posts by Evan Chen (陳誼廷)

12 thoughts on “Some Thoughts on Olympiad Material Design”

Victor Wang 8 April, 201715:30 Reply

FWIW I think the windmill problem is a perfect example of what you call Rigid (if you ignore the last line of the problem, and just focus on the process, how many different things can one actually try to prove?). But certainly many problems are hard to teach, or solve for that matter.
[BTW, regarding windmill in particular, you may also be interested in https://artofproblemsolving.com/community/c6h19770 (see my post for spoiler).]

Also, by Global you seem to really mean something like Local-to-Global (piecing together local info) as opposed to, say, leading order asymptotic analysis, though I may be wrong.

Cheers,
V

P.S. Thematic heuristics and intuition are definitely good, but I would also like to see more emphasis on *story* and *curiosity* in Olympiad culture—what/why things are interesting and how to ask better questions—in which case technique can play a helpful organizational role. In Expii (esp. Solve) problem tagging we often use both concrete topic tags and meta ones (often from https://www.expii.com/map/3624 or https://www.expii.com/map/3670 for instance), so that one could learn from either lens in principle (though meta is not a current priority for practical reasons).

LikeLiked by 1 person
1. Gray Sphere 8 April, 201719:55 Reply
  
  I have an idea of how we could make this a bit more concrete.
  
  Consider the following problem: 12% of a sphere is pained black. Prove there exists a cube inscribed in that sphere with all 8 white vertices.
  
  It can be solved via straightforward application of the probabilistic method: Inscribe a cube in the sphere at random. The indicator random variable of whether or not each vertex is black has expectation 0.12 so the expected number of black vertices is, by linearity of expectation, 0.96, so there must exist an inscribed cube with 0 black vertices or all 8 white vertices. The shortness of this solution makes it suitable for making the discussion very concrete.
  
  That being said, coming up with the above solution seems to be hard, unless one is very good at the probabilistic method, as I believe, if i recall correctly, that in Arthur Engel’s PSS, where the weaker problem for a rectangular prism is given, he states he doesn’t even know if the result is true for a cube. I had the pleasure of coming up with this solution when I was sufficiently unfamiliar with the probabilistic method to have to think hard about this problem. According to what you said in the previous article, this suggests that storing this problem as a cherished memory (which I do) should help me solve other problems which have no obvious relation to this one (problems which are not just one application of the probabilistic method, as I didn’t perceive this problem like that initially either) but which are connected to this problem via a “philosophy” of “what does this problem feel like”.
  
  I’m not sure if my initial motivation for this proof matches your “global” (and it wouldn’t be a perfect example because I had at least SEEN the probabilistic method before) but your description of “global” seems to include this problem, and enable one to solve it without having ever seen probabilistic method as long as they recall linearity of expectation and the fact that if the expected number of black vertices is 0.96, there must be a cube with 0 black vertices.
  
  Is this problem “global” (by the way no pun intended as the problem is about a sphere)?
  
  If so: Could you please explain how thinking about this problem in terms of your “global” would motivate the solution I gave (if we assume the solver knows the material and your global philosophy but either doesn’t know probabilistic method or cannot simply think “oh this is just probabilistic method”/”this is similar to tons of other probabilistic method problems I’ve done” – because my understanding is probabilistic method is a technical theme, and “global” is a broader heuristic)? What about the problem, to somebody who doesn’t realize probabilistic method is fundamentally suited to it, suggests it is a “global” problem?
  
  Thank you
  
  LikeLike
  1. Evan Chen (陳誼廷) 11 April, 201706:08
    
    I actually think of “probabilistic method” as just a common special case of my Global idea. So I think we are only differing in naming and are talking about the same thing.
    
    LikeLike
2. Evan Chen (陳誼廷) 11 April, 201706:02 Reply
  
  That is a fair point about the windmill problem, I hadn’t thought about it that way (then again I didn’t solve it, and just heard the solution second-hand, so maybe more accurate to say I hadn’t thought about the windmill problem at all). And yes, “local-to-global” might be more accurate — I’ve been using the shorter handle for my working memory’s sake but I agree it could mean other things.
  
  Regarding stories: I think this is hard in olympiad culture now because people very rarely talk about how they come up with problems in the first place (you’re probably the main exception to this). I think it’s partly due to a disconnect between the problem authors and the conestants (the former are generally much older). I agree it would be really cool if stories became a more common thing.
  
  LikeLike
Gray Sphere 8 April, 201719:56 Reply

Oops I meant the previous post as a generic post, not as a reply to Victor’s post. The question is addressed to Evan.

LikeLike
Felps 9 April, 201713:26 Reply

It’s kinda sad that Evan Chen is probably the only top problem solver who likes to write about thoughts process and heuristics. Dry questions (without any clear motivation), dry solutions (that doesn’t explain the heuristics) and antisocial/recluse gold medalists are a sad tradition in math competitions.

LikeLike
1. Evan Chen (陳誼廷) 11 April, 201706:09 Reply
  
  There are certainly others too (like Victor Wang above for example), though not as many as I wish there were. I just happen to get more publicity.
  
  LikeLike
GLGR 10 April, 201722:49 Reply

Dear Evan,

Thanks for an excellent post, as always. What you’re describing has been studying extensively in cognitive psychology under the umbrella-term “acquisition of expertise”. It may very well be that you are extremely familiar with everything I’m about to write, but just in case you didn’t have the chance to look into it I’d thought I’d throw a few links at you. For example, you write:

“The status quo is that people do bucket sorts based on the particular technical details which are present in the problem.”

One of the most famous studies in the field is Chi, Feltovich, Glaser “Categorization and representation of physics problems by experts and novices.” [1] They asked PhD’s, Profs, and undergraduate to solve problems in classical mechanics, and tried to probe their thought-processes. One of their interesting finds is that undergraduates tend to categorize problems based on the superficial details (the existence of springs, inclined-planes, etc.), whereas experts tend to categorize problems based on the physical principle they expect to use in the solutions (Newton’s second law etc.).

You wrote: “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.”

The same study also found that experts tend to spend more time at the beginning, evaluating the problem (trying to decide “what kind” it is); whereas the beginning undergraduates tend to jump into the fray, immediately trying to solve the problem with some equations.

Finally, you say that you “spend a lot of time trying to classify the main ideas into categories or themes,” and advocate “to keep a journal or blog of the problems you’ve done.” This is part of the process of chunking [2], and the thinking is that experts differ from non-experts in the complexity and quality of their chunks (one could chunk chunks, and iterating this is the “complexity”). In fact, the Russian school of chess ~30 years ago asked students to collect favourite positions on flash-cards, and have their analysis on the other side. The positions were supposed to be examples of typical situations/ideas/themes, in the same way you’re advocating keeping a journal of typical problems. [I don’t have a reference for this; I believe I’ve read it in a Jermey Silman book, but I’ll have to dig a little bit to find it.] Since chess can be easily separated into levels of expertise (based on the ELO rating), they are the subjects of a lot of chunking studies [Adriaan de Groot should be the first link in this rabbit-hole].

My apologies again if this is all old-hat to you =)

[1] http://onlinelibrary.wiley.com/doi/10.1207/s15516709cog0502_2/pdf
[2] https://en.wikipedia.org/wiki/Chunking_(psychology)

LikeLiked by 2 people
1. Evan Chen (陳誼廷) 11 April, 201705:57 Reply
  
  This is a fantastic reference, thanks! :) It’s great to see these ideas come out in a context other than math, and to have a name attached to them.
  
  For what it’s worth I haven’t seen any of this before, but even if I had I’m sure that other readers of the blog would have appreciated it. So thank you again for sharing.
  
  LikeLike
Anant Mudgal 25 April, 201715:31 Reply

I like this way of thinking about olympiad problems! A few thoughts here and there. Most prominently, I think “heuristics” leading to solutions should be emphasized for problems which are hard to sort by key ideas (for e.g. Windmill problem).

1. Aside from buckets, for non-standard geometry problems, looking at “how to construct” the diagram, and “degrees of dependence between points/lines etc” looks useful to me. I feel it should be stated more often.

Part of the reason I believe drawing good diagrams help is because it subconsciously inquires about how the elements in a diagram are linked with each other.

There is also the local-global way principle: Focusing solely on sub/super configurations is extremely helpful. I like the way you do it in your proposals! :)

2. As you pointed, combinatorics is very open-ended and lacks identifiable or recurring configurations as in geometry. I had like to know how you go about teaching this or what buckets you have here.

3. For FEs, i think teaching by main ideas has it’s gaps. Often times there is no central idea at all, it’s just about finding a needle in a haystack of equations. It is also very unlikely that any two [hard] FEs will have the same (or similar) idea(s).

As FEs are very open-ended (substitute whatever you want they say); it helps a lot to recognize whether to pursue substitutions or patch-up given equations with arguments on structure (I place them under “Subs” and “Structure” tags).

For e.g., in IMO 2015/5, it’s clear after a bit of work out that we can’t find anything about the structure of $f$, say, injectivity, surjectivity, increasing, bounded etc. And, the FE is very “restricted”: one can’t plug in values of $y$ beyond the $\pm 1$ spectrum, etc hoping for nicer equations. Meaning we just have to perform substitutions in the very few “standard” equations we get. An added (and crucial) insight about fixed points (motivated by $\text{id}$ being a solution) basically drains the entire difficulty of the problem.

Motivation here comes from the three tags: “Subs”, “Restricted”, and “equality case” (which motivates fixed points).

Issue is, each FE can have different insights so as such it’s hard to do taxonomy here. I am yet to find any counter-measure against it.

Your views on this will be very helpful!

LikeLike
Things I’ve learned from running OTIS – Power Overwhelming 3 November, 202313:37 Reply

[…] only works if you write well. When writing olympiad content, good taste in choosing problems and choosing themes is important, and the units are one of the biggest strengths of […]

LikeLike
MOHS was a mistake – Power Overwhelming 5 January, 202413:37 Reply

[…] that to guide my teaching. For a concrete example, see the story about TSTST 2016/4 at the end of this blog post, where lower-than-expected scores on TSTST 2016/4 gave me an idea for a new lesson […]

LikeLike