How to Approach an Olympiad Problem (by Ho Jun Wei)


The following article was written by Ho Jun Wei who was an IMO medalist in 2006. He has trained several members in the Singapore IMO team in the past and was my MO trainer when I was Sec 4. He is currently studying Mathematics in Cambridge University. The following post presents his insights in solving an MO problem.

In this post I shall provide several tips on how to tackle a long Olympiad problem, particularly those in SMO (senior/open) Round 2. While I draw my examples mainly from problems in number theory, the strategies I mention are very general and apply to most Olympiad problems. The opinions expressed in this post are entirely mine, and I accept that everyone has a different way of approaching problems. Here I’ll share some good problem solving habits I’ve picked up over the years, and feel free to share yours too. In trying to keep this article general and applicable to most types of problems, I’ve refrained from going into very specific methods for particular topics like combi or NT. I may talk about more specific techniques in a separate post later.

First, let’s get this clear: there is no substitute for practice. There is no shortcut to become really good at solving math Olympiad problems. I once coached a student who later achieved a remarkable 2nd place (internationally) and Gold medal at a recent IMO. You may know who I’m referring to. What’s his secret? He spends an average of several hours a day (often up to 4 or 5 hours) solving Olympiad problems. Over time, these hours put into solving problems will help you amass a huge vocabulary of Olympiad tricks, techniques, theorems and lemmas, and hone your problem solving intuition. Doing math Olympiad is very much like playing soccer. While a soccer match only lasts for 90 minutes, it is what happens before the match that truly decides the game – the hours put into training daily to gain incredible agility, stamina, and an impeccable technique. Of course, the strategies adopted during the 90-minute match are also important, but never as crucial as the training and preparation that comes before it. Even if you have very good match strategies, you won’t be able to execute them properly if you don’t have the required level of fitness or skill.  Fitness and skill comes with practice, and practice makes perfect.

A good Olympiad problem is one that uses very elementary techniques in very clever ways. It should not require the use of any very advanced math theorems, beyond the usual handful (e.g. Fermat’s Little Theorem, Ceva’s and Menalaus, AM-GM, etc.). There was an earlier post by Shi Jie that touches on these (refer to the links above), which I feel is a fairly comprehensive list (and you should make sure you already know most of these by heart). These theorems may prove very handy in some problems, but in fact many problems in SMO don’t even require the use of any of these theorems; they simply require keen observation or the clever applications of simple techniques like factorization, pigeonhole principle, or similar triangles. These simple techniques go a very long way. So my advice is to invest your time in mastering the basics and how to spot clever ways of using them, rather than learn fanciful stuff like quadratic reciprocity, group theory, Ramsey theory, solving geometry problems by inversion/complex numbers or proving inequalities using Lagrange multipliers, just to name a few. Practically all SMO problems can be solved using elementary methods and, occasionally, one or two basic theorems. The only non-standard method that I think may be useful is coordinate geometry, or vector geometry (don’t worry if you don’t know these) – but even these are not necessary because any problem that can be solved in this way can be solved using elementary methods as well.

In the course of coaching Math Olympiad, I find that many students commonly get stuck on a problem either because they don’t know how to get started, or they’ve run out of things to try after some time. The well-prepared problem solver would not face such situations: If you know your usual theorems, and know your basic tools and techniques, you should never really run out of things to try. You would first try to change or simplify the problem if possible, try small cases, then pick an approach, try to prove it and maybe fail, pick another approach or maybe try to prove a stronger result that you conjectured, find out that your conjecture was false, move on to another approach, etc. If you have tried enough Olympiad problems, you should be familiar with common tricks and techniques for particular topics, and you will be able to use these as a starting point for approaching problems.

Pre-match preparation: Theorems, Lemmas, Techniques

  1. You should already know all the usual theorems by heart, and if possible, understand the ideas behind their proofs as well. These theorems form part of the backbone of your thinking process. They are a crucial part of your toolbox.
  2. Build up your arsenal of lemmas. These are simple results that are not formal theorems, but can be very helpful in tackling more complex problems. For instance, did you know that the centroid G, circumcentre O and orthocenter H of a triangle are collinear, with GH=2OG? Or that x^2\equiv 1 \mod{p} has an integer solution x if and only if the prime p is of the form 4k-1? A sizeable collection of lemmas can only be built up by doing more problems. The more lemmas you know, the more tools you have at your disposal, the easier “standard” problems will become. The IMO team that I had the privilege of coaching had their personal self-compiled “handbook of geometry lemmas” and “100 standard inequalities” which they knew by heart, and that proved very useful because some hard problems became almost trivial once you knew one or two of these lemmas beforehand.
  3. Know your techniques!!! These are general methods or approaches to solving a particular type of problem. For instance, when faced with a polynomial problem, we can consider a polynomial in terms of its roots, in terms of its coefficients, or in terms of a quotient and remainder using the remainder-factor theorem. These multiple perspectives give us many things to try! For inequalities some common techniques are smoothing, expand-then-AM-GM or substitution. In geometry, a common technique is to draw one or more helping lines (cleverly chosen). Another usual approach is to show that certain points are concyclic / collinear, and there are other less standard methods like coordinate geometry. In combinatorics, things like pigeonhole principle, invariance principle, extremal principle, double counting, finding recursions or bijections are very useful. In number theory, techniques like modular arithmetic, bounding, factorization are widely used. For problems of the form “show that (something) is true for all integers n”, a viable technique may be induction. This is the most important point, because many students run out of things to try too quickly. With a large bag of techniques available, you will always have many approaches to pry a problem from different angles. This can only be attained by solving more Olympiad problems and learning new techniques. I will talk about general techniques for combinatorial problems in another post.

To illustrate what I mean by “the well-prepared problem solver never runs out of things to try”, let us look at an SMO (senior) 2004 problem: “Find all integer pairs (x,y) that satisfy (x^2-y^2)^2=1+16y“. It is a good habit to first find easy solutions like (\pm1,0). The fact that a solution exists already eliminates some possible approaches (like using modular arithmetic to prove the no solutions exist). It is easy to see that we only need to consider the case when x, y are non-negative, since (x, y) is a solution iff (-x, y) is a solution and clearly RHS > 0 so y \ge 0. It is also natural to first factorise the LHS as (x+y)^2(x-y)^2. At the start it is intuitive to try approaches like taking mod 16, or bringing the 1 to the LHS and factorising it as a difference of two squares to see if you can deduce anything (usually it gives some conditions on parity). Alternatively, you may try to consider cases when x or y is even or odd. Some students may run out of things to try at this point. However, if we had done enough of such problems, we’ll have many other things to try. For instance we can try particular cases by putting x=0 or x=y \pm 1, to see if these particular cases give any result or insight. Indeed we will find that x=y \pm 1 gives solutions. Another fairly standard approach is to find some bounds on the solutions (e.g. show that x or y or x+y cannot be too large). In this case, just by looking at the equation we can tell that if |x-y| becomes too large, then LHS > RHS so no solutions can exist. For instance, if |x-y|\ge 2 then LHS \ge 4(x+y)^2 \ge 4y|x+y|, so by comparing with RHS we find that |x-y|\le 4, which reduces it to just a few cases to check. In fact it turns out that we need |x-y|<2, thereby reducing the problem to a few cases that are easy to solve by hand (Exercise: Verify that the only solutions are (\pm 1,0), (\pm4, 3), (\pm 4, 5)).

If trying to bound the solutions didn’t work, some other possible ways we could have messed around with this problem are: take mod y, we get x^2=1 \mod {y} so maybe we can try substituting x^2=ky+1 and rewrite the expression as a quartic polynomial in y and try to factorise. Or we could conjecture that there are infinitely many solutions arising from a clever construction (e.g. like (x,y)=(m^2+m+1, m+1) for all integers m) which we would try to guess and derive. These approaches may not lead to anything useful, and our conjectures might be wrong, but at least we never run out of things to try. Given more experience, it is easier to tell what approaches may work, which ones will lead to a dead end, and what conjectures are more likely to be true, thereby making our problem solving process more efficient. The point is that we don’t run out of approaches to try.

During the match: How to be effective at your game

  1. Whenever possible, always try small cases (or extreme cases) first to make sure you understand the problem and see how it works, possibly obtaining trivial solutions (Note: In a geometry problem, “trying small cases” means drawing the diagram in different ways or considering degenerate cases, in inequalities it means trying to spot the equality case or testing extreme values). If you’re lucky, by trying small cases you may be able to spot a pattern or gain some insight as to why the problem works in a certain way, which could lead you to the solution. Or perhaps you could make a smart conjecture by observing small cases (as in the above NT problem, one might try out particular values e.g. x=y\pm 1 gives solutions, and trying x=y\pm 2 may help you realize that |x-y| cannot be too large).
  2. Restate the problem in different ways. A geometry problem that asks you to show that AB is perpendicular to CD may be a disguise for asking you to show that AC^2+BD^2=AD^2+BC^2 (check that the two conditions are indeed equivalent, this is a lemma!). This restates a problem of angles to one of length, which may be useful if the conditions in the problem give you information about length. An inequality problem may sometimes be transformed by means of a suitable substitution. In other words, try to write equivalent formulations of the same problem, thereby changing the original problem to something that’s possibly easier to prove. (take care to make sure that the new problem is indeed equivalent to, and not stronger than, the original!)
  3. “Wishful thinking”. This is a very useful strategy to keep in mind. By careful observation or by trying small cases you may conjecture that certain things may be true, upon which the problem would be a lot easier. For instance, one may wish “if only the circumcentre lies on this line…” or “if only this number is always a perfect square…” or one may conjecture, after trying small cases, that a particular function is surjective/monotonic. Another example: If you’re given a combi problem that asks “for what values of n does (a certain property) hold”? You might try small cases then guess that it works only when n is a triangular number or power of 2, for instance. Now try to prove that wish/conjecture, because it might just be true and make your life much simpler.
  4. Prove something stronger than the original problem. This is rare and difficult to spot, but sometimes can be the only way to solve a problem. For instance, Shi-Jie has shown in a previous post how some inequalities can be proven by proving a stronger inequality. There are some inductive proofs that work only if you prove a stronger statement (because it also strengthens your induction hypothesis).
  5. Don’t be too fixated on any particular approach too early in the game. When first exploring a problem, keep an open mind, think of different approaches to the problem, and see what information each of them will give you. Do not spend too much time on any single approach or conjecture, especially if you’re not sure it’s the right one. For instance, if you make a conjecture and try to prove it but keep failing, it may not even be true; try to disprove it instead. Having said that, don’t be a schizophrenic and keep jumping from one approach to another – you risk giving up the right idea too quickly. How long you should spend on one particular approach is a very subjective matter, and in fact it is a judgment skill that comes with experience i.e. more practice!
  6. Always try easy/obvious approaches first before moving on to more adventurous things.
  7. Look at the conditions or constraints given. If you haven’t used a particular condition yet, ask yourself why it may be helpful. If an inequality has constraints like xyz=1, it is useful for homogenizing or substitution. If it has a constraint like |x_i|\le 1, this may be a clue that you should use some trigonometric stubstitution. If a combi problem has conditions like “every two students did 5 questions in common”, then clearly you have to consider some suitable quantity where this constraint would give you some kind of equality/inequality. If you’re given a number theory problem like find all integer solutions (x,y) to 2^x+1=3^y, then taking mod 4 or mod 3 should be useful.

Finally, let’s look at a recent SMO (Open) 2010 problem: Let a_n, b_n, n=1, 2, 3, \cdots be a two sequences of integers defined by a_1=1, b_1=0 and for n \ge 1, we have a_{n+1}=7a_n+12b_n+6, b_{n+1}=4a_n+7b_n+3. Prove that a_n^2 is the difference of two cubes. How do we start to prove something like that? Clearly we don’t need stuff like Fermat’s Little Theorem or the Chinese Remainder Theorem here. The experienced problem solver will immediately see two viable strategies for this problem: induction on n (we still need to figure out what the hypothesis should be), or by clever manipulation / guesswork to guess a closed form for the recursive sequence. In any case, the most obvious thing to do first is to look at small cases: It is easy to work out that a_1=1, a_2=13, a_3=181 and b_1=0, b_2=7, b_3=104. We also find easily that a_1^2=1^3-0^3 and a_2^2=8^3-7^3. At this point, based on the n=1,2 cases the sharp problem solver might already have a suspicion and make a conjecture, which one can confirm using the n=3 case. If not, we can try to work out the cubes for n=3. It is less obvious what consecutive cubes this will give, because the numbers get big and unmanageable very quickly for large . But by letting a_3^2=(k+1)^3-k^3 and some simple calculations we obtain k(k+1)=2^3 \cdot 3 \cdot 5 \cdot 7 \cdot 13 which we easily solve to get k=104. Look at the value for b_3 again… smell something fishy? It becomes very natural to “wish” that a_n^3=(b_n+1)^3-b_n^3, which is true and very easy to show by induction. Moral of the story? Try small cases to see how the problem works! This is what I mean when I say that many SMO problems don’t require any theorems at all, but simply require astute observation skills and familiarity with elementary techniques and approaches for such problems.

If you’ve read the entire post till here, thanks for taking the time. I hope I managed to at least shed some light on how to approach an Olympiad problem. I’d like to reemphasize that the only way to improve is to do more problems (it’s good to look at solutions and learn from them when you’re completely stuck, or even when you managed to solve the problem). For starters, if you don’t know the usual handful of theorems, go learn them first. Then keep building up your bank of tricks, techniques and lemmas (for instance by reading this blog often and trying more problems), and you’ll find that in time to come, you won’t run out of ideas and approaches so easily when faced with these pesky long problems.

P/S: @Jun Wei Thanks for you contribution!

Cheers,

ksj


Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s