A Minimal Olympian Toolkit

Evan Chen

July 26, 2013

Contents

0 Introduction 5
0.1 Why Math is Hard . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
0.1.1 An Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
0.1.2 Three Introductory Problems . . . . . . . . . . . . . . . . . . . . . . . 6
0.2 Writing Proofs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
0.2.1 Scoring . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
0.3 Mathematical Induction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
0.3.1 What Induction Actually Is . . . . . . . . . . . . . . . . . . . . . . . . 9
0.3.2 Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
0.3.3 Final Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
0.3.4 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

1 Geometry 12
1.1 Computation in Triangles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.1.1 Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.1.2 Tools . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.2 Triangle Centers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.2.1 Vocabulary Lesson . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.2.2 Ceva’s Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.2.3 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.3 More on Length Chasing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.3.1 Back to MathCounts . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.3.2 Ptolemy’s Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.3.3 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
1.4 Angle Chasing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
1.4.1 Cyclic Quadrilaterals . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
1.4.2 Other Ways to Deal with Angles . . . . . . . . . . . . . . . . . . . . . 19
1.4.3 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
1.5 Fact 5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
1.6 TSTST 2012, Problem 7 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
1.7 The Champions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
1.8 Quiz Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
1.8.1 Quiz 1 Solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
1.8.2 Quiz 2 Solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

2 Combinatorics 28
2.1 Computation with Binomial Coefficients . . . . . . . . . . . . . . . . . . . . . 29
2.1.1 Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
2.1.2 The Many Faces of Binomial Coefficients . . . . . . . . . . . . . . . . 29
2.1.3 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
2.2 Recursions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
2.3 Bijections, Double Counting . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
2.3.1 Basic Ideas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

2
Evan Chen, IHS Math Training Contents

2.3.2 Proof by Story . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

2.3.3 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
2.4 Pigeonhole Principle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
2.5 Processes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
2.5.1 Invariants and Constructions . . . . . . . . . . . . . . . . . . . . . . . 35
2.5.2 Monovariants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
2.5.3 Coloring . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
2.5.4 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
2.6 Quiz Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
2.6.1 Quiz 1 Solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
2.6.2 Quiz 2 Solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

3
 The original purpose of this work was to provide a reader entering the world of mathe-
matical olympiads with the minimal tools necessary; that is, this is merely a compilation
of the most standard techniques available. The target difficulty ranges from mid-AIME to
mid-USAMO; at least this was the original intention. Over time, as this document increases
in length, so will the scope.
I hardly think I have any truly novel material here; I have merely drawn upon my never-
ending supply of problems and resources and tailored them to fit the group of students which
I am training. I confess to stealing problems and ideas from MOP handouts, AoPS texts,
and the MathLinks forums. I hope the authors of these do not mind, or better yet, never
find out.
On the other hand, I have tried to, when relevant, help students understand the motivation
beneath solutions, a task which I probably have failed miserably. I think most novices fall
into two category: those who stare at a problem, and those who try numerous strategies in
the hope that the problem will fall apart. This text is aimed at the latter; I hope to refine
both technique and intuition.
0 Introduction
0.1 Why Math is Hard
In the AMC’s and the AIME, speed and accuracy are the two important factors. You are all
smart enough to practice for these contests on your own. . . just do a bunch of old problems,
and if you hit one that you actually don’t know how to do (e.g. not arithmetic errors), spend
some time learning the solution so that you never miss a similar problem again. This takes
a LOT of time and dedication, but for smart students like you, there’s no magic to it.
Things are different at the olympiad level. Rather than simply going down a list of
techniques for each problem, one frequently has to invent new tactics on the spot, or modify
new ones, to suit the problem. Hard problems which ask you to prove X ⇒ Y are often
solved by showing X ⇒ A, A ⇒ B and finally B ⇒ Y . These problems are not hard because
the individual implications are hard. It is trying to figure out what A and B are that make
such problems very difficult.
When approached by olympiad problems there seem to be two issues that many run into:

(i) One does not know where to begin, and resorts to simply staring (or giving up alto-
gether).

(ii) One tries things at random in the hope that something will work.

If you are reading this, then I suspect the latter case is more likely. (Students who are
used to the comforts of school math, where one is told the answers in advance, tend to do the
first.) The aim is that, after some experience, you will begin to see that solutions to olympiad
problems do not magically appear from thin air: they are motivated by observations, by
insights, by intuition. I could go on and on. . . but let’s move to an example
(tl;dr: Don’t just stare, but try approaches which are most likely to work first.)

0.1.1 An Example
Example. Show that there are no integers a, b, c and n such that

a2 + b2 + c2 = 8n − 1.

If you haven’t spent a lot of time with olympiad number theory, you probably have no
clue how to start. That’s a good thing. Take a few moments, try out a couple of things,
play around with the problem. You’ll learn a lot more from the solution if you’ve spent at
least some time fighting with the problem.
The solution is on the next page.

5
Evan Chen, IHS Math Training Chapter 0. Introduction

Solution, with commentary. The first key observation is that the right-hand-side is really
just there for decoration. What is it actually saying? Well, think about it this way: for a
given k, when does there exist an integer n such that k = 8n − 1?. Answer: if and only if
k + 1 is divisible by 8. So the conditions in the problem don’t care about anything except
the remainder when a2 + b2 + c2 is divided by 8. Cool, we can get rid of n without losing
any information; one less variable to worry about.
I’ll introduce a bit of notation here: I’ll write a ≡ b (mod m) if m divides a − b. Basically
this is just remainder stuff: I would write 2012 ≡ 2 (mod 10) because the remainder when
2012 is divided by 10 is 2.
Anyway, now the problem statement seems a little surprising. The problem is actually
telling me that if I take any three squares and add them, I will never get 7 (mod 8). Ever.
Think about this for a moment– it would seem that if I have that much control over a2 +b2 +c2 ,
surely I could get something which is 7 (mod 8). For heaven’s sake, I get to pick three
numbers!
Well, let’s see how far I can get with just one square. (If I want to understand a2 + b2 + c2 ,
I had better at least understand a2 .) Out of just curiosity, I write:

02 ≡0 (mod 8)
2
1 ≡1 (mod 8)
2
2 ≡4 (mod 8)
32 ≡1 (mod 8)
2
4 ≡0 (mod 8)
52 ≡1 (mod 8)
2
6 ≡4 (mod 8)
2
7 ≡1 (mod 8)

At this point I can stop, because I only care about the remainder (mod 8). (If I asked
you for the possible last digits of squares, you would only check 02 through 92 . The same
idea applies here).
OK, well, it looks like I actually don’t have that much control, because I can only get 0,
1 or 4. In other words, my possible remainders (mod 8) are pretty restricted.
Wait, actually, I’m done. . . I just have to check that I can’t make 7 as a sum of three
members of {0, 1, 4}, and there’s only a finite number of cases.

Of course, in the above solution I only wrote down the things things I tried which worked.
You had better believe there are other dead ends that look like reasonable approaches.

0.1.2 Three Introductory Problems

The most important thing for the following problems is that you do not try strategies at
random; you make a move because it will improve your position. Intuition is valuable here!

1. (Poland) Let f : R → R be a continuous function such that f (x)f (f (x)) = 1 for each
x. Given that f (1000) = 999, determine f (500).

2. Prove that n(n + 1) is not a perfect square for any integer n ≥ 1.

3. (Czech-Slovak, adapted) Find, with proof, all functions f : R → R with the following
two properties:

6
Evan Chen, IHS Math Training Chapter 0. Introduction

• f (x) is not zero whenever x is not zero.

• f (x2 + y) = f (f (x) − y) + 4f (x)y for all real numbers x and y.

7
Evan Chen, IHS Math Training Chapter 0. Introduction

0.2 Writing Proofs

It occurred to me the other day while I was writing this that most of you have very little
experience writing mathematical proofs. The best advice I can give is to find the “How to
Write a Solution” article on AoPS and read it through. Since I would mostly be repeating
it, I’ll just make a few comments about things which bother me more than others.

• Do not use two-column proofs. I’m sure you’re happy to hear this as well. You’re
welcome.

• Use English words! There is no reason to communicate in hieroglyphics when both

the reader and writer speak a natural language. Mathematical notation is meant to
facilitate explanations, not to replace them.

• Write forwards, even if you found the solution by working backwards. The solutions
will be much easier to read this way.

• Be neat.

Actually that’s all I really have to say. The second point is something a lot of people seem
to not realize: your solutions should not look like your scratch paper.1 .
One last note: the solution earlier to the problem about a2 + b2 + c2 = 8n − 1 was meant to
help with learning. It is by no means a well-written solution, which should be more direct.
To conclude this section, I’ll rewrite the proof as I would on an actual test:

Solution. Assume for contradiction a solution exists, and take mod 8. Note that the right-
hand side is 7 (mod 8). On the other hand, the possible residues of a square modulo 8 are
0, 1 and 4, and one can check that there are no three elements of {0, 1, 4} (not necessarily
distinct) which yield a sum of 7 (mod 8). Therefore, we are done.

While it’s much harder to see where this solution came from, the method of attack is much
more clear. (This is also why reading solutions in not necessarily a good way of learning. . . )

0.2.1 Scoring
On that topic, let me mention something about scoring. Whenever I grade a proof, I assign
two scores: one is a math score out of seven points, and the other is a style score, which is
an integer between 1 and 10 divided by 10. The math score reflects whether the solution is
correct and complete. The style score doesn’t count for anything, but it’s an indication of
how elegant and well-written your solution is.

1
Unless you’re at the IMO (where your team leaders can defend you), and you have VERY neat scratch
paper. Which some people do.

8
Evan Chen, IHS Math Training Chapter 0. Introduction

Sc Description Sc Description
7 Correct and complete 1.0 I’m buying you a cake
6 Extremely minor flaw 0.9 Very elegant solution
5 Minor flaw 0.8 Pretty nice solution
4 Very rare 0.7 Most solutions
3 Very rare 0.6 Meh
2 Has many, but not all, of the main ideas 0.5 Serious stylistic issues
1 Has found some of the main ideas 0.4 Lagrange Multipliers
0 Very common ≤ 0.3 Intentionally written to annoy grader

Table 0.1: Math Scores Table 0.2: Style Scores

0.3 Mathematical Induction

0.3.1 What Induction Actually Is
Induction is one of the most powerful tools we have, because it allows us to utilize previous
instances of a statement to prove later ones. Unfortunately, in school it is often taught as a
mindless procedure to be regurgitated on problems involving sums, and strong induction is
not even mentioned.
For completion, here is the statement of the principle:

Theorem 1 (Strong Induction). Let P (n) be a proposition. Suppose that P (1) is true, and
for all n we have the implication

P (1), P (2), · · · , P (n − 1) ⇒ P (n)

Then P (n) is true for all n.

Note that this is somewhat more powerful than the induction you are likely familiar with,
when you only get P (n − 1) ⇒ P (n).
Thinking about induction in this direction tends to be counter-intuitive, though. A much
more natural way to say this is:

If you can always reduce the problem to a smaller case, then you are done.
From this point of view, there is no reason to ever not use strong induction (in favor of regular
induction): you should be thinking about reducing n to something smaller, and there’s no
reason you should be aiming for n − 1. Your goal is to get something smaller; while n − 1
tends to be the most common, there’s no reason to explicitly focus on it.

0.3.2 Example
n(n+1)
The amusing example 1 + 2 + · · · + n = 2 is left to the reader. We will do a more
interesting problem:

Example (Canada 1987). Let n > 1 be an odd integer. n people are standing on a field
with water guns, such that the distances between them are all different. Each person shoots
the other person closest to them. Prove that at least one person is left dry.

A bit of initial scouting shows that the result is obvious for n = 1 and n = 3 but false
when n = 2. On further consideration it’s not hard to see the result is false for all even n,
so any strategy we try had better take this into account.

9
Evan Chen, IHS Math Training Chapter 0. Introduction

The tip-off that induction might help is that the “smaller cases” are more or less embedded
into the “larger cases” (in terms of structure, at least). Also, it’s hard to manage all n people
at once. So how can we induct?
Let’s look at all the distances and take the pair of people which are closest together.
Obviously they shoot each other (and hence are dry), so we don’t really care about them.
If we remove them, there had better still be at least one person dry. Can we prove this?
Oh wait, this section is on induction, and what we’ve actually done is reduced the case n to
n − 2. So we don’t actually have to “prove” this; rather, we may assume it. We’re done!
Well, almost. There’s just a little bit of detail we need to sort out. First, if n is odd, then
n − 2 is odd, so we’re fine there. Also, what if the people we removed were shot more than
once? Could this screw up our induction? Well, not really. . . if someone was dry before,
they’ll still be dry if we add in two people who just shot each other.
Time to write up a solution.

Proof. We will prove the result by induction on odd n. Our base case n = 3 is obvious.
Consider n people, and let A and B be the pair which minimizes the distance AB. These
two people will shoot each other. Looking at the other n − 2 people, we see by the induction
hypothesis (note that n − 2 is also odd) that at least one person, say P , will not be shot
(while it’s possible that they will shoot A or B, this does not affect the claim). Since A and
B shoot each other, this implies that P will be dry.
This completes the induction step and solves the problem

0.3.3 Final Notes

First, there are plenty of ways to vary an induction. You could have more than one base
case, for example. There are also forms of induction to the effect of P (n) ⇒ P (2n), P (n) ⇒
P (n − 1) (why does this work?). Don’t be too eager to pick one in advance.
When writing an induction proof, your first sentence should announce that you are in-
ducting, and probably what you are inducting on (in this case n). If you are using strong
induction, you should mention this as well.
Also, you should explicitly mark off what the base/inductive steps are, as well.

0.3.4 Exercises
n(n+1)(2n+1)
1. Show that 1 + 2 + · · · + n2 = 6 .

2. Prove that every positive integer is the product of primes.

n
3. Show that 3n+1 divides 23 + 1.

4. n cities are connected by n bridges. Show that there is a loop.

5. (Classical) Let n ≥ 1 be an integer. A 2n ×2n chessboard has one of its squares removed.
Prove that it is possible to tile the rest of the board completely with L-dominoes.

Figure 0.1: This is an L-domino.

6. (FLT) Let p be an odd prime and n ≥ 1 be an integer. Prove that p divides np − n.

10
Evan Chen, IHS Math Training Chapter 0. Introduction

7. Prove the AM-GM inequality: for positive reals x1 , x2 , · · · , xn we have

x1 + x2 + · · · + xn √
≥ n x1 x2 · · · xn .
n
(Hint: show P (n) ⇒ P (2n) and P (n) ⇒ P (n − 1).)

11
1 Geometry
Initially your stumbling block is going to be not knowing the right tools to solve a problem.
This will hopefully change very quickly. Once it does, you’re back to the old “How would I
have thought of that?”
I’ve never found a particularly satisfying answer for this question, partially because I don’t
claim to understand what “geometric intuition” is. I hope the answer is not “recognizing
known configurations”; however, this turns out to be an extremely important skill in many
problems1 . One of the most famous is Yufei Zhao’s “Cyclic Quadrilaterals – The Big Picture”,
which can be found online at http://yufeizhao.com/olympiad/cyclic_quad.pdf. If you
are comfortable with everything in the first few sections, you should read this instead.
Those of you who are just setting out should take the time to learn the basic tools well
first. I think I’ve included the majority of them here. Anyways, here are some general tips.

• Draw large, in-scale diagrams, if you can afford the time. Note the pluralization!
At worst, this will prevent you from trying to prove something that is false. At best,
this will suggest something that is true. (This is why drawing more than one diagram
is helpful.)

• Work both forwards and backwards. One of the really nice things about geometry
is that you can often go in both directions. If you keep a list of things you know and
things you want, you are done the moment something appears on both lists.

• Simplify the problem. In that vein, you can often work backwards and simplify the
end condition. If you can eliminate entire points or entire lines, this is usually a good
thing. Problem 7 from the TSTST 2012 is a really good example of this which I will
show you later.

• Phantom points. Let’s say ABC is inscribed in ω, D is the intersection of ω with

some line `, and you want to prove D lies on a line `2 . It’s often easier to let `1 and `2
intersect at D0 and try to prove that ABCD0 is cyclic.

• Use all the givens. Occasionally there will be a screwball problem where one of the
conditions isn’t necessary, but usually you do need all the conditions. If you haven’t
used all the conditions, then there’s no way you can solve the problem.

• Mark information as you find it. If two important angles are equal, draw them in.
If a quadrilateral is cyclic, make a note of this; I like to circle the four points rather
than try and draw in a circumcircle. (And for this, I usually use different colored pens).

1
Cough 2012 TSTST, Problem 4.

12
Evan Chen, IHS Math Training Chapter 1. Geometry

1.1 Computation in Triangles

1.1.1 Notation
Let ABC be triangle. Let a, b, c denote the lengths BC, CA, AB. Let K denote the area
of ABC. Let s = a+b+c 2 . Let R be the radius of the circumcircle of ABC, called the
circumradius, and let r bet he radius of the incircle of ABC, called the inradius.
For arbitrary points X, Y , and Z, [XY Z] will denote the area of XY Z.

1.1.2 Tools
These are all pretty useful things to know. They also happen to be not too difficult to prove,
so I will let you attempt to do so.

1. (Extended Sine Law) Prove that

a b c
= = = 2R
sin A sin B sin C
a
by showing sin A = 2R, via constructing a diameter with one endpoint at C.

2. (Areas) Prove that

p
K= s(s − a)(s − b)(s − c)
1 1 1
= ab sin C = bc sin A = ca sin B
2 2 2
= sr
abc
=
4R

3. (Stewart’s Theorem2 ) Let D be a point on BC. Denote n = DC, m = DB and

d = AD. Prove that
man + dad = bmb + cnc

The above lemmas are useful for computational geometry; in particular, the second one
lets you solve for r and R given a, b, c, etc., and so on.

2
A man and his dad put a bomb in the sink.

13
Evan Chen, IHS Math Training Chapter 1. Geometry

1.2 Triangle Centers

1.2.1 Vocabulary Lesson
Let ABC be a triangle. Then

Definition. The orthocenter of ABC, usually denoted by H, is the intersection of the

perpendiculars from A to BC, B to CA and C to AB.

Definition. The centroid of ABC, usually denoted by G, is the intersection of the lines
joining the midpoint of a side with the opposite vertices (i.e. the medians).

Definition. The incenter of ABC, usually denoted by I, is the intersection of the angle
bisectors of the angles of ABC. It is also the center of a circle tangent to all three sides,
called the incircle.

Definition. The circumcenter of ABC, usually denoted by O, is the center of the unique
circle passing through ABC, which is called the circumcircle.

In a few moments, you will prove that these points do exist.

1.2.2 Ceva’s Theorem

A cevian is a line joining one of the vertices of a triangle to a point on the opposite side.
There is a nice criterion for when three cevians are concurrent, as follows:

Theorem 2 (Ceva). In 4ABC, point D, E, and F lie on BC, CA and AB. Then AD,
BE and CF concur if and only if
BD CE AF
= 1.
DC EA F B

F
E
P

B D C

Figure 1.1: Ceva’s Theorem. The cevians concur at a point P .

Exercise. Let P be a point on the cevian AD of triangle ABC.

BD [BP D] [BAD]
(i) Prove that DC = [DP C] = [DAC] .

BD [BP A]
(ii) Use the above to show that DC = [CP A] .

(iii) Use this to deduce Ceva’s Theorem.

14
Evan Chen, IHS Math Training Chapter 1. Geometry

1.2.3 Problems
1. (Trig Ceva) Let AD, BE and CF be cevians of a triangle ABC. Prove that they
concur if and only if
sin ∠BAD sin ∠CBE sin ∠ACF
= 1.
sin ∠CAD sin ∠ABE sin ∠BCF

2. Let ABC be a triangle and denote by M the midpoint of BC. A point P is selected
on AM . BP meets AC at J, and CP meets AB at K. Show that JK k BC.

3. Prove that the centroid, orthocenter, circumcenter, and incenter all exist, using either
Ceva or Trig Ceva, or otherwise.

15
Evan Chen, IHS Math Training Chapter 1. Geometry

1.3 More on Length Chasing

1.3.1 Back to MathCounts
Here are some things to remember from MathCounts geometry! I mention them briefly
because I assume you are familiar with them.

• Similar Triangles: I’m sure you know what these are. Similar triangles provide a
link between ratios and angles by the AA, SAS and SSS criteria for similarity. Know
them when you see them.

• Pythagorean Theorem: Useful on the AIME. Please tell me you know what this is.
It does see occasional usage on olympiads.

• Law of Cosines: Generalizes the Pythagorean Theorem. Quite useful on the AIME.

• Tangents: The two tangents from a point to a circle are equal in length, and form
right angles with the center. Know this.

• Angle Bisector Theorem: If the angle bisector of ∠BAC hits BC at D, then

DB AB
DC = AC . Like similar triangles, this gives you a way of converting equal angles into
a ratio of sides.

• Power of a Point: We’ll go over this in more detail with cyclic quadrilaterals, but
you should know the statement of this! Let ω be a circle and P be a point. Suppose `
through P intersects ω at A and B; then the power of P with respect to ω is defined
as P A · P B, and does not depend on the line `.
Usually, the power is defined as positive when P is outside the circle and negative when
it is inside.

These are all very useful for side-chasing.

1.3.2 Ptolemy’s Theorem

When dealing with cyclic quadrilaterals, Ptolemy’s Theorem often provides a base for com-
puting side lengths.

Theorem 3 (Ptolemy’s Theorem). Let ABCD be a cyclic quadrilateral. Then AB · CD +

AD · BC = AC · BD.

Sketch of Proof. Ptolemy can actually be deduced by Stewart’s Theorem (and vice-versa).
Let P be the intersection of the diagonals and apply Stewart on triangle ABC with cevian
BP , in the form
AB 2 · P C BC 2 · P A
 
AP · P C
AC + PB = +
PB PB PB
Then use similar triangles.

Exercise. Complete the proof above!

16
Evan Chen, IHS Math Training Chapter 1. Geometry

1.3.3 Problems
1. (Mu-Alpha-Theta 1991) Given triangle ABC, compute tan C given

a3 + b3 + c3
= c2 .
a+b+c

2. Show that the medians of a triangle partition it into six triangles of equal area.

3. The side lengths of a triangle are 30, 40 and 50. What is the length of the shortest
altitude?

4. (Ray Li) Let ABC be a triangle. The angle bisector of ∠A meets BC at D and the
circumcircle of ABC at E. If AB = 36, BC = 40, CA = 44, compute DE 2 .

17
Evan Chen, IHS Math Training Chapter 1. Geometry

1.4 Angle Chasing

Angles are very useful in geometry. This section is dedicated to exploring how to use angles
properly.

1.4.1 Cyclic Quadrilaterals

Cyclic quadrilaterals come up EVERYWHERE. It’s just plain hard to do geometry if you
don’t understand the basics of how circles and angles interact.

Definition. A quadrilateral is said to by cyclic if it can be inscribed in a circle.

Here are the main results:

Theorem 4. Let ABCD be a quadrilateral. ABCD is cyclic if and only if

(i) ∠DAC = ∠DBC

(ii) ∠ABC + ∠ADC = 180◦ .

C
D

Figure 1.2: Bob the cyclic quadrilateral. Mark ALL the angles.

You should recognize the first two statements as trivial consequences of the Inscribed
Angle Theorem3 . However, it is extremely important to recognize that the converse of these
statements are all true! Furthermore, we have from a few sections ago:

Theorem 5 (Power of a Point). A, B, C, and D lie on a circle in some order. Let P be

the intersection of lines AC and BD. Then P A · P C = P B · P D. This quantity is called the
power of P with respect to the circle, and is negative when P is inside the circle and positive
otherwise.

Exercise. (This is very useful.) Suppose you are instead given P = AC ∩BD and P A·P C =
P B · P D. When is it true that ABCD is cyclic?

Power of a Point is useful because it gives both a way to find a new cyclic quadrilateral,
as well as use an old one. Obviously it is quite useful for things involving lengths.
When are cyclic quadrilaterals useful? Some instances when they are likely to show up:

• Multiple points on a circle. Three points determine a circle; if you have more than
this, then you have a bunch of equal angles for free.

3
If you don’t know what this is, find out very soon.

18
Evan Chen, IHS Math Training Chapter 1. Geometry

• Right angles. Pairs of right angles form cyclic quadrilaterals. (Why?) Not only that,
but when you have right angles in a circle, this means you get diameters.

• Angles. Particularly equal ones.

• The problem is olympiad geometry. Maybe not so much the AIME, but if you’re
doing a decently hard olympiad problem, there’s very often a cyclic quadrilateral some-
where.

1.4.2 Other Ways to Deal with Angles

Here are two other useful facts.

Fact. The sum of the angles in a triangle is 180◦ .

Fact. P lies on the opposite side of AB as C. P A is a tangent to the circumcircle of ABC

if and only if ∠P AB = ∠ACB.

P A

B
C

Figure 1.3: Tangent

1.4.3 Problems
The usual warning about motivation here: you should not immediately go bananas marking
angles every time you see a cyclic quadrilateral. Keep your eye on the prize.
Despite how much I’ve said this is a huge amount of beginning geometry, you will notice
there are not that many problems here. In fact, what actually happened was that the
problems section here got so large that I split most of it off into later sections, leaving only
a few of the easier problems here.

1. Prove that cyclic trapezoids are isosceles, and vice-versa.

2. Let ABC be a triangle with altitudes AD, BE, CF meeting at the orthocenter H.
(a) Among the seven points A, B, C, D, E, F and H, one can find six cyclic quadri-
laterals. What are they?
(b) Show that the altitudes of ABC are the angle bisectors of DEF .
(c) (Almost nine-point circle) Point H is reflected over sides BC, CA and AB to points
A1 , B1 and C1 in that order. Also, suppose HBCA2 , HCAB2 and HABC2 are
parallelograms. Prove that ABCA1 B1 C1 A2 B2 C2 is a cyclic nonagon (probably
self-intersecting).
(d) (Nine-point circle) Prove that the circumcircle of DEF passes through the mid-
points of the sides of ABC, as well as the midpoints of AH, BH and CH.

19
Evan Chen, IHS Math Training Chapter 1. Geometry

3. (Russia 1996) Points E and F are on side BC of convex quadrilateral ABCD (with E
closer than F to B). It is known that ∠BAE = ∠CDF and ∠EAF = ∠F DE. Prove
that ∠F AC = ∠EDB.

20
Evan Chen, IHS Math Training Chapter 1. Geometry

1.5 Fact 5
One particularly common configuration that you should know involves excircles. The A-
excircle is the circle tangent to side BC and the extensions of sides AB and AC through B
and C, respectively, and its center is the A-excenter. The B and C excircles and excenters
are defined similarly.

1. Let ABC be a triangle with incenter I, and let IA , IB , and IC be the A, B and
C-excenters.
(a) Show that IB IC bisects the exterior angle of A.
(b) Show that I is the orthocenter of triangle IA IB IC .

2. (Fact 5) Let ABC be a triangle. The incircle of ABC touches BC at a point D. The
A-excircle of ABC touches AB, AC, and BC at points XB , XC and E, and has center
J. Finally, the angle bisector of ∠A hits the circumcenter of ABC at L.

B D E C
XC

XB

Figure 1.4: Fact 5

(a) Prove that A, I, L and J are collinear.

(b) Compute AXB and AXC .
(c) Show that BD = EC = s − b and BE = DC = s − c.
(d) Show that L is the center of a circle passing through I, J, B and C.

21
Evan Chen, IHS Math Training Chapter 1. Geometry

1.6 TSTST 2012, Problem 7

To finish the geometry chapter, here’s a documentation of my thought process against a
fairly tough geometry problem as I solve it. This was not the solution I found during the
test.
Problem (TSTST 2012). Triangle ABC is inscribed in circle Ω. The interior angle bisector
of angle A intersects side BC and Ω at D and L (other than A), respectively. Let M be the
midpoint of side BC. The circumcircle of triangle ADM intersects sides AB and AC again
at Q and P (other than A), respectively. Let N be the midpoint of segment P Q, and let H
be the foot of the perpendicular from L to line N D. Prove that line M L is tangent to the
circumcircle of triangle HM N .

Q
N

D M C
B

H
L

Figure 1.5: Problem 7

Solution, with commentary. Well, first things first; that stupid tangent condition should be
rewritten. Rewrite it as ∠DN M = ∠HM L.
Maybe right now you remember that BL = LC from an earlier problem; if not, the
diagram should be a big hint. Anyways, it’s not too hard to see that ∠DM L = 90◦ . On
the other hand, we are told ∠DHL = 90◦ . Bam, cyclic quad! (Told you these things show
up everywhere.) So DM LH is cyclic, and now ∠HDL = ∠HM L. So we just want to prove
∠DN M = ∠HDL.
Wait a minute, that’s just saying M N k AD. And we know this has to be true for the
problem to be true. But this means that we can erase a whole bunch of things: namely H,
L, and a bunch of the lines related to them, leaving us which a much simpler problem.
OK, so how do we prove M N k AD? Hmm. . .

22
Evan Chen, IHS Math Training Chapter 1. Geometry

What’s the hardest part of this problem? It’s that darn circle passing through D and M ,
cutting the sides at P and Q, which at the moment we really know nothing about. What
can we do?
. . . And now here’s the insight (aka the hard part of the problem). D and M are pretty
good points in terms of lengths, so let’s apply Power of a Point to try and get a grip on P
and Q. We have

BQ · BA = BD · BM
CP · CA = CD · CM

But BM = CM , and BD BA
CD = CA . So this actually implies that BQ = CP ! Some of you
with better diagrams might have noticed this right off the bat, which is just as well.
OK, so M N is nowthe “average” of these two equal lengths. Hmm. . . in vector language,
M~N = 12 BQ ~ + CP~ . But if BQ = CP , then BQ ~ + CP ~ is parallel to the angle bisector,
namely AD, so M N must be as well. And suddenly the problem is solved!

Now, I’ve made the problem sound very easy. It’s really not. I ended up throwing barycen-
tric coordinates at this during the test after struggling with it, without success, for 90 min-
utes. But hopefully now you see that these solutions do come from somewhere, and what
you should be thinking about while you’re doing other problems.
By the way, it is true that H lies on the Γ. In fact, if you let X be the second intersection
of the two circles, it turns out that X lies on lines M L and N H. (Try and prove this!) This
leads to a solution using an idea called spiral similarity, which some veterans would recognize
instantly. (Remember the problem from the “Angle Chasing” section? Yes, same thing. It
also appears in Yufei Zhao’s “Cyclic Quadrilaterals– the Big Picture” which I mentioned
much earlier.)
Here’s a concise solution to the problem, and what should be submitted at an exam.
Remember that solutions should be written forwards.

Solution. First, we claim that M N k AD. Notice that, by Power of a Point and the Angle
Bisector Theorem, we have
BD · BM CD · CM
BQ = = = CP
BA CA
 
so BQ = CP . Now M~N = 12 BQ ~ + CP~ , and since BQ = CP it follows that M N is
parallel to the angle bisector of ∠BAC, namely AD.
Note that BL = LC ⇒ ∠DM L = 90◦ . Since ∠DHL = 90◦ , it follows that DM LH is
cyclic. Now ∠HM N = ∠HDL = ∠HM L, and the conclusion follows.

23
Evan Chen, IHS Math Training Chapter 1. Geometry

1.7 The Champions

Now that you have most of the tools, most problems are fair game. Good luck!

1. Let ω1 and ω2 be circles which intersect at points P and Q. AC is a chord of ω1 and

BD is a chord of ω2 . Suppose AC and BD intersect on P Q. Prove that ABCD is
cyclic.

2. (JMO 2011) Points A, B, C, D, E lie on a circle ω and point P lies outside the circle.
The given points are such that (i) lines P B and P D are tangent to ω, (ii) P, A, C are
collinear, and (iii) DE k AC. Prove that BE bisects AC.

3. (Mandelbrot 2012) Let ABC be a triangle inscribed in circle ω with BC = 17. The
angle bisector of ∠BAC intersects ω again at P . Given that sin ∠ABP = 35 , and that
the radius of ω is 20, compute the area of quadrilateral ABP C.

4. (USAMO 2010) Let AXY ZB be a convex pentagon inscribed in a semicircle of diameter

AB. Denote by P , Q, R, S the feet of the perpendiculars from Y onto lines AX, BX,
AZ, BZ, respectively. Prove that the acute angle formed by lines P Q and RS is half
the size of ∠XOZ, where O is the midpoint of segment AB.

5. (IMO 2012) Given triangle ABC the point J is the centre of the excircle opposite the
vertex A. This excircle is tangent to the side BC at M , and to the lines AB and AC
at K and L, respectively. The lines LM and BJ meet at F , and the lines KM and
CJ meet at G. Let S be the point of intersection of the lines AF and BC, and let T
be the point of intersection of the lines AG and BC. Prove that M is the midpoint of
ST.

6. (Brazil 2006) Let ABC be a triangle. The internal bisector of ∠B meets AC in P . Let
I be the incenter of ABC. Prove that if AP + AB = CB, then AP I is isosceles.

7. (Euler Line) In 4ABC, M is the midpoint of BC and AD is an altitude. Let H, G

and O be the othrocenter, centroid, and circumcenter.
(i) Prove that AM/GM = 3. (The AM-GM inequality will not help here.)
(ii) Prove that AG/GM = 2.
(iii) Let X and Y be the midpoints of AB and AC. By using similar triangles M XY
and ABC, show that AH = 2OM .
OG
(iv) Prove that O, G, and H are collinear, and compute HG .
(v) Prove that the center of the nine-point circle N is the midpoint of OH.

24
Evan Chen, IHS Math Training Chapter 1. Geometry

1.8 Quiz Problems

1. In quadrilateral ABCD, AB = 7, BC = 15, CD = 20, DA = 24, and BD = 25. Find
CA.

2. In the figure, 4ABC is divided into six smaller triangles, four of whose areas are
shown. Compute the area of 4ABC.

84

35
40 30
A B

3. Let ABCDE be a convex pentagon such that

∠BAC = ∠CAD = ∠DAE and ∠ABC = ∠ACD = ∠ADE.

Diagonals BD and CE meet at P . Prove that AP bisects CD.

4. Let ABCD be a cyclic quadrilateral. Denote by X and Y the orthocenters of ABD

and ACD. Prove that BC = XY .

1. Let ABC be an acute triangle with circumcenter O, orthocenter H, and incenter

1
I. Suppose that AH, BI, and CO concur and cos A cos B cos C = 64 . Compute
1000 cos B.

2. In triangle ABC, D is on AC and E is on AB such that:

(i) Triangle ADE and quadrilateral BCDE have equal area and perimeter.
(ii) Quadrilateral BCDE is cyclic.
(iii) AD = 20 and CD = 12.
√
The length of the altitude from A to BC can be expressed as k, for some positive
integer k. Find k.

3. Let ABC be a triangle with incenter I. A point P in the interior of the triangle satisfies

∠P BA + ∠P CA = ∠P BC + ∠P CB.

Show that AP ≥ AI, and that equality holds if and only if P = I.

25
Evan Chen, IHS Math Training Chapter 1. Geometry

1.8.1 Quiz 1 Solutions

1. In quadrilateral ABCD, AB = 7, BC = 15, CD = 20, DA = 24, and BD = 25. Find
CA.

Solution. Notice that ABCD is cyclic since ∠A = ∠C = 90◦ . Then by Ptolemy’s

Theorem, AC = 7·20+15·24
25 = 020 .

2. (AIME 1985) In the figure, 4ABC is divided into six smaller triangles, four of whose
areas are shown. Compute the area of 4ABC.

84

35
40 30
A B

Solution. We set the left blank area to y, and set the right blank area to x. Using the
fact that triangles with similar altitudes, we see that if we have AB as the base, we
get 124+y 30
65+x = 40 ⇒ y =
4x−112
3 .
y 70+y
Using AC as the base, we get 84 = 119+x .
Solving, we obtain x = 70, y = 56. Hence, the total area is 56 + 70 + 35 + 30 + 40 + 84 =
315 .

3. (ISL 2006 G3, by Zuming Feng) Let ABCDE be a convex pentagon such that

∠BAC = ∠CAD = ∠DAE and ∠ABC = ∠ACD = ∠ADE.

Diagonals BD and CE meet at P . Prove that AP bisects CD.

Solution. Observe that ABC, ACD, and ADE are all similar. From this it is not hard
to see that quadrilaterals ABCD and ACDE are similar. Denoting K = BD ∩ AC
AK AL
and L = CE ∩ AD, we find that KC = LC . The conclusion now follows via Ceva’s
Theorem.

4. (Evan Chen) Let ABCD be a cyclic quadrilateral. Denote by X and Y the orthocenters
of ABD and ACD. Prove that BC = XY .

Solution. (Aaron Lin) Reflect X and Y over side AD to points X 0 and Y 0 , which lie
on the circumcircle of ABCD. Now notice that BCY 0 X 0 is a cyclic trapezoid; hence
it is isosceles, so we have BC = X 0 Y 0 . Upon noticing XY = X 0 Y 0 we are done.

26
Evan Chen, IHS Math Training Chapter 1. Geometry

1.8.2 Quiz 2 Solutions

1. Let ABC be an acute triangle with circumcenter O, orthocenter H, and incenter
1
I. Suppose that AH, BI, and CO concur and cos A cos B cos C = 64 . Compute
1000 cos B.

Solution. Apply Trig Ceva to obtain

sin (90 − C) sin(B/2) sin (90 − A)
=1
sin (90 − B) sin(B/2) sin (90 − B)
1
This implies that cos2 B = cos A cos C, so cos3 B = cos A cos B cos C = 64 ⇒ 1000 cos B =
250 .

2. (WOOT Mock AIME 2011, by David Stoner) In triangle ABC, D is on AC and E is

on AB such that:
(i) Triangle ADE and quadrilateral BCDE have equal area and perimeter.
(ii) Quadrilateral BCDE is cyclic.
(iii) AD = 20 and CD = 12.
√
The length of the altitude from A to BC can be expressed as k, for some positive
integer k. Find k.

Solution. Since ∠EBC = ∠ADE we see that triangles ADE and ABC are similar. √
Furthermore, the ratio of their areas
√ is 1 : 2, so the√ratio of their side lengths
√ is 1 : 2.
It follows that AE = √12 AC = 16 2 and AB = 20 2, so that EB = 4 2.
√
The condition on the perimeter now gives BC = AE + AD − BE − DC = 8 + 12 2.
From here we can compute the height from A to BC because we know all the side
lengths of ABC. One approach is to compute [ABC] using Heron’s Formula and
divide by AB. Alternatively, let AL be the altitude, and write h = AL, x = BL and
y = CL. Then we obtain the system:
x2 + h2 = 800
y 2 + h2 = 1024
√
x + y = 8 + 12 2
224√
√
Subtracting the first two equations gives y 2 − x2 = 224 ⇒ y − x = 8+12 2
= 12 2 − 8,
√
and from here we obtian x = 8, y = 12 2, so h2 = 736 .

3. (IMO 2006, by Hojoo Lee from South Korea) Let ABC be a triangle with incenter I.
A point P in the interior of the triangle satisfies
∠P BA + ∠P CA = ∠P BC + ∠P CB.
Show that AP ≥ AI, and that equality holds if and only if P = I.
1
Solution. It is immediate that ∠P BC + ∠P CB = 2 (B + C), so ∠BP C = 90 + A/2.
Similarly, ∠BIC = 90 + A/2, so BIP C is cyclic.
Let AI meet the circumcircle of ABC at L. By Fact 5, P lies on a circle centered at
L passing through B, I and C. But A, I and L are collinear, implying the conclusion.

27
2 Combinatorics
If there was every a “miscellaneous” category for the IMO Shortlist, it must have been
renamed to “combinatorics” at some point. The field is very broad, and there at once many
standard techniques, and very few standard techniques.
Most of the sections will have very short theoretical portions, and consists of mostly
problems.

28
Evan Chen, IHS Math Training Chapter 2. Combinatorics

2.1 Computation with Binomial Coefficients

Binomial coefficients are no less useful now than they were back at MathCounts, particularly
in the AIME. I will assume you are at least familiar with them.

2.1.1 Definitions
The number of ways to select k objects from a set of n objects is denoted
 
n n!
=
k k!(n − k)!

Exercise. If you don’t know how to prove this, do so now.

Also, if you were not already aware, the name arises from the following identity:

Theorem 6 (Binomial Theorem). For all positive integers n,

n  
n
X n
(x + y) = xn−k y k
k
k=0

Exercise. Prove this.

n


2.1.2 The Many Faces of k

The following problems should help demonstrate just how versatile this tool is:

1. Determine the number of ways to choose four questions to do on a test of eleven.

2. How many ways can I rearrange the letters of AAAABBBBBBB?

3. What is the probability I get exactly 4 heads after flipping 11 coins?

4. How many paths are there from (0, 0) to (7, 4) that only go 1 up or 1 right? One
example is to go right twice, up 5 times, left twice, then up twice again.

5. I have 7 grape flavored lollipops that I want to distribute among the 5 members of my
school’s math team. In how many ways can I do that if I want everyone to get at least
zero lollipops?

It should be fairly clear that the answer to the first two questions is 11


4 , while the answer
(11)
to the third question is 2411 . What about the last two questions?

Counting Lattice Paths

The fourth problem can be answered by simply noting that a path consists of a sequence of
7 moves to the right, and 4 moves up. That is, it is the number of ways to rearrange the
11


sequence RRRRRRRU U U U . Thus, the answer is also 4 .
An alternate method is to label (0, 0) with the number 1, and from there, label every point
(a, b) with the sum of the labels on points (a − 1, b) and (a, b − 1). These numbers represent
the number of ways to reach that point from (0, 0). Do you get a familiar pattern?
See http://www.artofproblemsolving.com/Videos/external.php?video_id=73 for a
more verbose explanation.

29
Evan Chen, IHS Math Training Chapter 2. Combinatorics

Balls and Urns

Problem. I have 7 grape flavored lollipops that I want to distribute among the 5 members
of my school’s math team. In how many ways can I do that if I want everyone to get at least
zero lollipops?

This is a famous problem with a very nice trick, called balls and urns or stars and bars.
Imagine laying the 7 lollipops out in a line and then taking 4 pencils and
inserting them into the line to use as dividers. We then give all the lollipops to the
left of the first divider to the first student, all the lollipops in between the first divider and
the second divider to the second student, and so on until we give all the lollipops to the
right of the last divider to the fourth student. The distributions of lollipops resulting from
distinct arrangements of pencils and lollipops will be distinct, and furthermore every possible
distribution of lollipops among the students corresponds with an arrangement of lollipops
and pencils.
For instance, the arrangement **|*|**||** (where a | is a pencil and a * is a lollipop)
corresponds to giving two lollipops to the first, third, and fifth person, one to the second,
and none to the fourth.
Thus our answer is just the number of ways to arrange the lollipops and the
pencils, which is the number of
ways to select 4 locations to place pencils out of a total of
7 + 4 = 11 objects, which is 11 4 .
This generalizes to

Theorem 7 (Balls and Urns). The number of way to place b balls in u urns is
 
b+u−1
.
u−1

2.1.3 Exercises
√
4
1. Compute 14641.

2. Compute
n  
X n
.
k
k=0

3. In the above problem about grape lollipops, what happens if I want to be nice and
make sure everyone gets at least one lollipop?

4. How many ordered pairs (a, b, c, d)
of odd, positive integers satisfy a + b + c + d = 2012?
Leave your answer in the form nk .

5. (HMMT 2012) A frog is at the point (0, 0). Every second, he can jump one unit either
up or right. He can only move to points (x, y) where x and y are not both odd. How
many ways can he get to the point (8, 14)?

30
Evan Chen, IHS Math Training Chapter 2. Combinatorics

2.2 Recursions
These are close friends on the AIME. If you can compute an in terms of an−1 , an−2 , · · · then
you are more or less done. Often you can find an explicit formula for an ; other times, n will
be small enough that you can go after it directly.
Reiterating the point about AIME. . . take this with a grain of salt, but a combinatorics
problem with a small integer is a really big hint that recursion could help.

1. Let Qn denote the number of ways of placing n rooks on an n-by-n chessboard so that
the arrangement is symmetric about the diagonal from the upper-left to lower-right
corner, and no two rooks are attacking each other. Prove that

Qn = Qn−1 + (n − 1)Qn−2 .

2. Let T0 = a, and for n > 0, Tn = nTn−1 + b · n!. Derive a closed-form expression for Tn
in terms of n, a, and b.

3. (AMC 12A 2007) Call a set of integers spacy if it contains no more than one out of any
three consecutive integers. How many subsets of {1, 2, 3, . . . , 12}, including the empty
set, are spacy?

4. (AIME 1995) What is the probability that in the process of repeatedly flipping a fair
coin, one will encounter a run of 5 heads before one encounters a run of 2 tails?

5. (AIME 2008) Consider sequences that consist entirely of A’s and B’s and that have
the property that every run of consecutive A’s has even length, and every run of
consecutive B’s has odd length. Examples of such sequences are AA, B, and AABAA,
while BBAB is not such a sequence. How many such sequences have length 14?

6. (AIME 2001) A mail carrier delivers mail to the nineteen houses on the east side of
Elm Street. The carrier notices that no two adjacent houses ever get mail on the same
day, but that there are never more than two houses in a row that get no mail on the
same day. How many different patterns of mail delivery are possible?

31
Evan Chen, IHS Math Training Chapter 2. Combinatorics

2.3 Bijections, Double Counting

It wasn’t until I was writing this that I realized just how related this ideas all were. I had a
hard time deciding whether to call something double counting or bijecting, so I mashed the
two sections together.

2.3.1 Basic Ideas

Bijections
You’ve already seen an example of a bijection: balls and urns. Formally, a map f : A → B is a
bijection if it is both injective (that is, f (x) = f (y) ⇒ x = y, and surjective ∀y∃x : f (x) = y.
In other words, there exists an inverse function. When A and B are finite this implies
|A| = |B|.
Putting the formal nonsense aside, the basic strategy is to take something we want to count
and biject it something much easier to count. In balls and urns, we bijected the possible
ways of placing balls into urns to sequences of stars and bars.
The same idea solves all the following problems.

Double Counting
A similar idea is called double counting, or counting in two ways. Many bijections can be
rephrased in this more general principle.
The idea is that if you count the same thing in two different ways, the two quantities must
be equal. OK, this is obvious and silly, but let’s look at a couple examples, and you’ll see
what I’m saying.

2.3.2 Proof by Story

Here are some bijective proofs.
Example. Prove that nk = n−k n



.
Proof by Story. George the farmer has n cows and needs to sacrifice k to Miss
Chung.

He
n n
can either pick k cows to sacrifice, or pick n−k cows to save. So we see that k = n−k .

Example (Pascal’s Identity). Prove that n−1 n−1

= nk .




k−1 + k

Proof by Story. George the farmer is in the same predicament. One of his cows is named
Taf. George doesn’t want him to go, but Taf is fat and Miss Chung likes big steaks. If George
decides to give away Taf, then he has to pick k−1 more cows from the other n−1. Otherwise,
he can let Taf go back to the barn, and is now faced with
choosing which

k n−1
of the

other
n−1
n n−1 n
cows to pick. The total number of ways to do this is k . Hence k−1 + k = k .

The last example is probably actually double-counting.

Example. Evan is passing back Alice, Bob, Carol and Dave’s tests. He doesn’t know
anyone’s names, so he passes them back randomly. Let N be the number of people who get
their own test back. Find the expected value of N .
Solution. In 4! = 24 alternate universes, Evan hands back each test in one of the possible
orders. He gets Alice right exactly 3! = 6 times; namely, universes ABCD, ABDC, ACBD,
ACDB, ADBC, ADCB. He also gets Bob, Carol, and Dave right exactly 3! = 6 times. So
in total, he gets 24 hits over the 24 alternate universes. Since each universe is exactly as
likely to happen, the expected value of N is 1 .

32
Evan Chen, IHS Math Training Chapter 2. Combinatorics

2.3.3 Problems
1. Prove that
Pn n

n
(a) k=0 k = 2 .
Pn n 2
= 2n



(b) k=0 k n .
Pn n

n−1 .
(c) k=0 k · k = n · 2

2. (AHSME 1989) Suppose that 7 boys and 13 girls stand in a line. Let N be the number
of places where a boy and a girl are standing next to each other. Determine the
expected value of N .

3. (AIME 1983) For {1, 2, 3, . . . , n} and each of its nonempty subsets a unique alternating
sum is defined as follows: Arrange the numbers in the subset in decreasing order and
then, beginning with the largest, alternately add and subtract successive numbers.
(For example, the alternating sum for {1, 2, 4, 6, 9} is 9 − 6 + 4 − 2 + 1 = 6 and for {5}
it is simply 5.) Find the sum of all such alternating sums for n = 7.

4. (AIME 2010) Determine the number of integer solutions to a + 10b + 100c + 1000d =
2010, where 0 ≤ a, b, c, d ≤ 99 are integers.

33
Evan Chen, IHS Math Training Chapter 2. Combinatorics

2.4 Pigeonhole Principle

Fact (Pigeonhole Principle). If kn + 1 pigeons are placed in n holes, then there is a hole
with at least k + 1 pigeons.

This is an obvious fact, but it has a name because the idea appears often. Its role is similar
to induction: it is a very general tool, so you need to know when it is applicable. The tip-off
that induction might be useful is when smaller cases have similar structure to larger cases.
The trigger for pigeonhole is more subtle; one example might be an existence problem in
which you have a lot of freedom (i.e. the conclusion does not seem very strong.)
Of course, there is nothing restricting us to integers. If a1 + a2 + · · · + an = S are reals,
there is some i such that ai ≤ S/n, etc.

1. In the set {1, 2, · · · , 2n}, one selects n + 1 numbers. Prove that there are two selected
numbers which are (a) relatively prime, (b) one of which divides the other.

2. There are n positive integers a1 , a2 , · · · , an . Prove that there exists integers i < j such
that n|ai + · · · + aj .

3. Five points are in a unit square. The shortest distance between any two points is d.
What is the largest possible value of d?

4. A positive integer d is given. Prove that there is an integer a such that the set {a, a +
d, a + 2d, · · · } has infinitely many primes.

5. (USAMO 2012) A circle is divided into 432 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.

6. (USAMO 2012) For integer n ≥ 2, let x1 , x2 , . . . , xn be real numbers satisfying

x1 + x2 + . . . + xn = 0, and x21 + x22 + . . . + x2n = 1.

For each subset A ⊆ {1, 2, . . . , n}, define

X
SA = xi .
i∈A

(If A is the empty set, then SA = 0.)

Prove that for any positive number λ, the number of sets A satisfying SA ≥ λ is at
most 2n−3 /λ2 .

34
Evan Chen, IHS Math Training Chapter 2. Combinatorics

2.5 Processes
2.5.1 Invariants and Constructions
Invariant problems usually aren’t too disguised. You’ll see what I mean in the examples. . . An
invariant is something that does not change upon a certain operation. As a textbook example:

Example. The numbers between 1 and 2011 inclusive are written on a blackboard. Every
second, Alice erases two numbers a and b, and writes either a + b or a − b in their place. The
process continues until we reach a single number. Determine which of the numbers we can
reach:

(a) 55555

(b) 666666

(c) 7777777

(d) 88888888

Solution. Consider the sum of the numbers on the board at any given time, and notice that
the parity does not change under the operation. Hence, the parity is an invariant. Since the
sum 1 + 2 + · · · + 2011 is initially even, the ending number must be even as well. Hence, we
cannot reach any of the odd numbers.
Are we done? No, we still need to prove that we can actually reach the even numbers. And
in fact it turns out that we can’t reach the last number, since the last number is essentially
of the form ±1 ± 2 ± 3 · · · ± 2011 < 88888888.
On the other hand, 666666 is achievable, although the actual construction is a rather
annoying computation. Check that

666666 = 1164 + 1165 + · · · + 1333 + 1335 + 1336 + · · · + 2011 − (1 + 2 + · · · + 1163 + 1334).

From here the answer is clear.

Notice that the criteria for proving something is impossible and proving something is
possible are quite different. To prove something is impossible, we just need to find one
invariant that breaks under the operations. On the other hand, to prove that something is
possible, we usually have to explicitly construct it (often induction is also a viable method
for construction).

2.5.2 Monovariants
Your age is a monovariant: it always increases. Therefore you will eventually die. Here is a
more serious example:

Example. 2000 people are in a mansion with a finite number of rooms. Every minute,
someone walks from one room to another room with at least as many people. Prove that
eventually, everyone will be in one room.

Solution. The result seems obvious, but trying to prove it rigorously is not trivial. If you
try to think about people moving locally, the problem is pretty maddening. Monovariants
give us a way to look at the problem globally: let xi be the number of people in room i and
consider the quantity X
K= x2i .
i≥1

35
Evan Chen, IHS Math Training Chapter 2. Combinatorics

We claim this keeps increasing. It’s not 2

2 2 2
P hard to2prove that when m ≤ n, we have (m − 1) +
(n + 1) > m + n . However, K < i≥1 2000 , so K is always finite. But K increases by
at least one, so this process must terminate. It can only terminate when everyone is in one
room.

Exercise. Modify the last part of the proof so it holds for infinitely large mansions.

2.5.3 Coloring
Color a board in a useful way. Enough said.

Example (Knight’s Tour). Can a knight visit every square of a chessboard exactly once,
ending at the square opposite from which it started?

Solution. No. The knight makes exactly 63 jumps, and each jump changes the color of the
square it is on.

2.5.4 Problems
1. In a 8 × 8 chessboard, two opposite corners are removed. Determine whether the
remaining 62 squares can be tiled by 2 × 1 dominoes.

2. Let ABCDEF be a hexagon. Let x1 , x2 , · · · be a sequence of real numbers. At time

t = 0, the numbers 1, 0, 1, 0, 0, 0 are written at the vertices of ABCDEF in that order.
For each integer time t afterwards, an edge ABCDEF is randomly selected, and xt
is added to the endpoints of that edge. Determine whether it is possible that at time
t = 2011, the six vertices of ABCDEF are all zero.

3. Can one cover a 10 × 10 chessboard with tetris T -pieces?

4. The points A = (−1, −1), B = (1, −1) and C = (−1, 1) are given. At each step, one
may pick one of the points X, and move X to any other point X 0 so that XX 0 is
parallel to the line through the other two points. In the end, one obtains an equilateral
triangle. Determine all possible side lengths of that triangle.

5. (USAMTS) The Rational Unit Jumping Frog starts at (0, 0) on the Cartesian plane,
and each minute jumps a distance of exactly 1 unit to a point with rational coordinates.
(a) Show that it is possible for the frog to reach the point 51 , 17
1


in a finite amount
of time.
(b) Show that the frog can never reach the point 0, 41 .

6. (Russia, adapted) Three piles of stones are given, with sizes 13, 3 and 7. Miss Chung
decides to play a game with her Honors Pre-Calculus class. A move consists of moving
one stone from one pile to another. Per move, Miss Chung adds k points to their next
test, where k is the difference (possibly negative) between the sizes of the receiving
and original pile, not counting the stone that is currently being moved. What is the
maximum possible number of points the students can accumulate?

7. (Putnam) Given n red points and n blue points, no three collinear, prove that it is
possible to join each red point to a blue point in such a way that none of the segments
formed have an intersection.

8. (IMO 1975) Let S(N ) be the sum of the digits of N . Compute S(S(S(44444444 ))).

36
Evan Chen, IHS Math Training Chapter 2. Combinatorics

2.6 Quiz Problems

1. N = 100! is given. How many zeros are at the end of the decimal representation of
N?

2. A collection of 8 cubes consists of one cube with edge-length k for each integer k,
1 ≤ k ≤ 8. A tower is to be built using all 8 cubes according to the rules:
• Any cube may be the bottom cube in the tower.
• The cube immediately on top of a cube with edge-length k must have edge-length
at most k + 2.
Let T be the number of different towers than can be constructed. What is the remainder
when T is divided by 1000?

3. Let N be the number of people in the world, not necessarily alive, who have received
an odd number of handshakes. Prove that N is even.

4. Let A be any set of 20 integers chosen from the arithmetic progression {1, 4, 7, · · · , 100}.
Prove that there are distinct integers in A with sum 104.

1. 5050 students are to be arranged into 100 teams. The first team has 1 member, the
second team has 2 members, etc. (The order of the students in a team is irrelevant.)
Let N represent the number of ways to arrange all the students. Compute the number
of zeros at the end of the decimal form of N .

2. The positive integers between 1 and 12 n(n + 1) inclusive are arranged at random into n
rows. The first row has 1 number, the second has 2 numbers, the third has 3 numbers
and so on. Find the probability that the largest number in each row is smaller than
the largest number in each row with more numbers.

3. Let n be a positive integer. Determine the number of polynomials P (x) with coefficients
in {0, 1, 2, 3} such that P (2) = n.

37
Evan Chen, IHS Math Training Chapter 2. Combinatorics

2.6.1 Quiz 1 Solutions

1. N = 100! is given. How many zeros are at the end of the decimal representation of
N?

Solution. It suffices to find the exponent of 5 in 100! (since the exponent of 2 is clearly
larger). But there are 20 elements divisible by 5 and 4 elements divisible by 25 (i.e.
with an additional exponent of 5.) Hence, the answer is 20 + 4 = 24 .

2. (2006 AIME I) A collection of 8 cubes consists of one cube with edge-length k for each
integer k, 1 ≤ k ≤ 8. A tower is to be built using all 8 cubes according to the rules:
• Any cube may be the bottom cube in the tower.
• The cube immediately on top of a cube with edge-length k must have edge-length
at most k + 2.
Let T be the number of different towers than can be constructed. What is the remainder
when T is divided by 1000?

Solution. Let’s construct the tower by starting with the cubes with side lengths 1, 2,
and 3 in any order. There are 6 = 2 · 31 ways to do this. Now, by induction, we claim
that there are 2 · 3k−2 ways to stack k cubes legally. We already have the base case,
and for the inductive step, we just need to show that there are 3 ways to stack k cubes
for each stack of k − 1 cubes. Consider cube k. It can be on top of cubes k − 1 or k − 2
or on the bottom. Since each of these corresponds to a unique stack, and it covers all
legal stacks, induction is complete. That way, with 8 cubes, the number of ways is

2 · 36 = 1458 ≡ 458 (mod 1000).

3. Let N be the number of people in the world, not necessarily alive, who have received
an odd number of handshakes. Prove that N is even.

Solution. Let A be the number of handshakes in the world given, and let f (p) be the
number of handshakes a person p has received. Note that
X
2A = f (p).
people p

Taking modulo 2, we get 0 ≡ N (mod 2), hence the conclusion.

4. (Putnam 1978) Let A be any set of 20 integers chosen from the arithmetic progression
{1, 4, 7, · · · , 100}. Prove that there are distinct integers in A with sum 104.

Solution. Consider the seventeen sets {4, 100}, {7, 97}, · · · , {49, 53} in conjunction with
the singleton sets {1} and {52}. These sets partition A. Since we select 20 elements
from A, we must have selected two elements from one set; since in each of the pairs,
the sum is 104, the conclusion follows.

38
Evan Chen, IHS Math Training Chapter 2. Combinatorics

2.6.2 Quiz 2 Solutions

1. (Evan Chen) 5050 students are to be arranged into 100 teams. The first team has 1
member, the second team has 2 members, etc. (The order of the students in a team is
irrelevant.) Let N represent the number of ways to arrange all the students. Compute
the number of zeros at the end of the decimal form of N .

Solution. Line up all 5050! ways to arrange the students into teams where order is
relevant. To compensate for overcounting, we divide that number by 1! · 2! · 3! · · · 98! ·
99! · 100!. In other words:

5050!
N= 100
Y
k!
k=1

Let v5 (x) the exponent of 5 in the prime factorization of x. For instance, v5 (3) = 0
and v5 (242 · 31337 · 59001 ) = 9001. Then the quantity we seek is v5 (N ) (since there
are strictly more factors of 2 anyways.) Note that v5 (xy) = v5 (x) + v5 (y) and the
well-known v5 (x!) = bx/5c + bbx/5c /5c + · · · from the previous test.
Then we have:
Y 
v5 (N ) = v5 (5050!) − f k!
100
X
= v5 (5050!) − v5 (k!)
k=1
100 X
X k
= 1261 − v5 (j)
k=1 j=1
100
X
= 1261 − ((101 − k)v5 (k))
k=1
= 1261 − (96v5 (5) + 91v5 (10) + · · · + 6v5 (95) + 1v5 (100))
= 1261 − (96 + 91 + · · · + 1) − (76 + 51 + 26 + 1)
= 1261 − 970 − 154
= 137 .

2. (Canada 1990) The positive integers between 1 and 12 n(n + 1) inclusive are arranged
at random into n rows. The first row has 1 number, the second has 2 numbers, the
third has 3 numbers and so on. Find the probability that the largest number in each
row is smaller than the largest number in each row with more numbers.
2n
Solution. We prove that the answer is (n+1)! by induction. The base n = 1 is evident.
For the inductive step, note that the largest number must be in the last row. This
n 2
occurs with probability n(n+1) = n+1 . For the remaining numbers, notice that we can
2
simply relabel them, so by the inductive hypothesis the remaining n−1 rows are sorted
n−1
with probability 2 n! . So now,
2 2n−1 2n
· =
n+1 n! (n + 1)!

39
Evan Chen, IHS Math Training Chapter 2. Combinatorics

completing the induction.

3. (China 1996) Let n be a positive integer. Determine the number of polynomials P (x)
with coefficients in {0, 1, 2, 3} such that P (2) = n.

i.
P
Solution. Let P (x) = i≥0 ai x We can write this as

P (2) = (a0 + 4a2 + 16a3 + · · · ) + 2 (a1 + 4a3 + 16a5 + · · · )

Now each quantity in parantheses can be viewed as a base-4 number. So the answer
is the number of nonnegative integer solutions to n = 2a + b. We can pick a to be
anything betwen 0 and bn/2c, so the answer is bn/2c + 1.

40