How to nuke combo problems, by a combo

main
Amogh Akella
August 2023

§1 Introduction
This handout will cover general methods such as grid colorings, the Pigeonhole Principle,
and expected value. While these topics are no doubt most useful in olympiads, these can
also be applied to computational competitions, and they are generally good to know.

§2 Colorings
We will begin with perhaps the most simple, yet useful topic: Colorings.
Arguably, the best way to teach is by example. Therefore, we will start with one: the
infamous 2023 JMO Problem 4.

Example 2.1 (JMO 2023/4)

Two players, B and R, play the following game on an infinite grid of unit squares,
all initially colored white. The players take turns starting with B. On B’s turn, B
selects one white unit square and colors it blue. On R’s turn, R selects two white
unit squares and colors them red. The players alternate until B decides to end the
game. At this point, B gets a score, given by the number of unit squares in the
largest (in terms of area) simple polygon containing only blue unit squares. What is
the largest score B can guarantee?
(A simple polygon is a polygon (not necessarily convex) that does not intersect
itself and has no holes.)

This problem seems simple, like most J4s. Additionally, it is not hard to arrive at the
answer, 4. But, how do we prove this?
Surprisingly, about 10% of the participants solved this problem correctly in-contest.
Here is the intended solution, but with motivation, as many people I know complained
after the contest that the solution was unmotivated.
Firstly, it is clear that B can guarantee 4. We will now show that R has a strategy to
restrict B to 4.
After playing around with the problem, you may notice that R can do very well if he
keeps on playing on the perimeter of the blue region. This motivates us to consider a
strategy where we, say, choose a lattice point P , and block off each blue square on its
sides facing away from P . In particular, if we choose P as the bottom right corner of the
first square that B places, it is very hard for B to expand his region. In fact, we can
add to the strategy that when B plays adjacent to the 2-by-2 square centered at P , R

1
Amogh Akella — August 2023 How to nuke combo problems, by a combo main

plays on the other side of the adjacency edge. This strategy is enough to ensure that
this particular blue region never gets an area of greater than 4. The following solution is
straightforward to find after this:

Proof. It is clear that B can guarantee a score of 4. We will show that R can restrict B
to 4. Partition the grid into 2-by-2 squares. Whenever B plays in some 2-by-2 square S,
we instruct R to place two red squares in the spaces that are adjacent to B’s square but
not in S. It is clear that no two blue squares in different 2-by-2 regions can be adjacent.
Therefore, we conclude that the maximum possible score for B is 4, the area of a 2-by-2
square.

This proof can teach us two important lessons. Firstly, that most combo problems
are trivialized or at least made simpler by some sort of coloring (or in this case grid
partitioning, basically the same thing). Secondly, when given a difficult combo problem,
often you should just play around with the problem and see where it takes you.

Example 2.2 (IMO Shortlist 1999/C2)

A tile is made of 5 unit squares as shown. Show that if a 5 x n rectangle can be
covered with n tiles, then n is even.

This is another good example of using the coloring method in an olympiad problem.
We should probably color the grid somehow in two colors, say black and white. But
how? The checkerboard pattern does not seem to yield anything.
The key observation for this problem is that each tile is almost a square. We can use
this observation by coloring the first row, the third row, and the fifth row black, and the
rest white. Observe that each tile covers three squares of one color and two of the other
color. This is especially useful because there are 3n black squares and 2n white squares
in the rectangle, meaning that each tile must cover exactly three black squares. The
proof is not difficult to finish from here:

Proof. Color the first, third, and fifth row black. Observe that each tile must cover three
squares of one color and two of another color. However, since there are 3n black squares
and 2n white squares, we conclude that each tile must cover exactly 3 black squares.
Therefore, for odd n, we see that there must be some tile that covers squares on both
the second and the fourth row. However, this tile must cover three white squares, a
contradiction.

This is a short, simple proof, but it is not necessarily easy to find. This proof teaches
us another important lesson: when choosing a coloring, you should choose a coloring that
takes advantage of the problem or at least gives you something nontrivial rather than a
common coloring such as the checkerboard pattern, which is often not useful.

Problems for this section:

Problem 2.3 (JMO 2014/5). Let k be a positive integer. Two players A and B play a
game on an infinite grid of regular hexagons. Initially all the grid cells are empty. Then
the players alternately take turns with A moving first. In his move, A may choose two
adjacent hexagons in the grid which are empty and place a counter in both of them. In

2
Amogh Akella — August 2023 How to nuke combo problems, by a combo main

his move, B may choose any counter on the board and remove it. If at any time there
are k consecutive grid cells in a line all of which contain a counter, A wins. Find the
minimum value of k for which A cannot win in a finite number of moves, or prove that
no such minimum value exists. Hints: 2, 6
Problem 2.4 (EGMO 2017/3). There are 2017 lines in a plane such that no 3 of them
go through the same point. Turbo the snail can slide along the lines in the following
fashion: she initially moves on one of the lines and continues moving on a given line until
she reaches an intersection of 2 lines. At the intersection, she follows her journey on the
other line turning left or right, alternating the direction she chooses at each intersection
point she passes. Can it happen that she slides through a line segment for a second time
in her journey but in the opposite direction as she did for the first time? Hints: 4, 7

§3 Pigeonhole Principle
The Pigeonhole Principle is another basic and seemingly obvious theorem, but its
applications are far from trivial.

Theorem 3.1 (Pigeonhole Principle)

If n pigeons are put into k holes, then at least one hole must contain at least ⌈ nk ⌉
pigeons, and at least one hole must contain at most ⌊ nk ⌋ pigeons.

Proof. Suppose the contrary to the first statement. Then, the number of pigeons is at
most k(⌈ nk ⌉ − 1) < k nk = n. A similar proof proves the second statement.

Example 3.2 (Paul Erdos)

Show that if n + 1 numbers are chosen from the set {1, 2, . . . , 2n}, then there exist
two numbers p and q in this set such that p|q.

Proof. We express each number m as am bm , such that am is a power of 2 and bm is an

odd number, which could be equal to 1. Observe that there are n possible values of bm ,
but n + 1 numbers, therefore there must exist some numbers p and q such that p < q
and bp = bq . Therefore, p|q.

This should already be enough for you to see the importance of the Pigeonhole Principle:
we have successfully solved a nontrivial problem using a trivial theorem. In fact, this is
the only elementary and short solution to this problem as far as I know.

Example 3.3 (USAMO 2018/4, JMO 2018/5)

Let p be a prime, and let a1 , . . . , ap be integers. Show that there exists an integer k
such that the numbers
a1 + k, a2 + 2k, . . . , ap + pk
produce at least 12 p distinct remainders upon division by p.

Proof. We assume that p is odd, since the case with p = 2 is trivial. We impose the
additional restriction that 0 ≤ k ≤ p − 1, which does not change the problem. Define

3
Amogh Akella — August 2023 How to nuke combo problems, by a combo main

sk to be the number of pairs of integers that are the same mod p among the integers
a1 +k, a2 +2k, . . . , ap +pk. For every pair of integers am , an , it is obvious that there exists
exactly one k such that am + mk = an + nk (mod p). Therefore, the number of pairs is
exactly p(p−1)
2 . By the Pigeonhole principle, there must exist some integer m such that
the number of pairs in m is at most p−1 2 . Group the numbers a1 + k, a2 + 2k, . . . , ap + pk
into sets based on their values mod p, and remove all but one element from each set.
Observe that each removal breaks at least one pair, and at most p−1 2 removals can be
made. This means that there are at least p − p−1 2 = p+1
2 groups, completing the proof.

The above solution is really simple, and yet only half of the contestants managed to
solve the problem. This shows how powerful the Pigeon-hole principle can be!

§3.1 Problems for this section:

Problem 3.4 (Andrew Vázsonyi, Marta Sved). Suppose we are given n integers a1 , . . .,
an , which need not be distinct. Prove that there exists a set of consecutive numbers
ak + 1, ak + 2, . . . , al , whose sum is a multiple of n. Hints: 3
Problem 3.5 (Japan MO 1997/1). Prove that among any 10 points in a circle with
diameter 5, there exist at least two with a distance of at most 2 from each other. Hints:
1, 5

§4 Expected value and the Probabilistic Method

Example 4.1 (Mathcounts Nationals Countdown Round 2018)

In a barn, 100 chicks sit peacefully in a circle. Suddenly, each chick randomly pecks
the chick immediately to its left or right. What is the expected number of un-pecked
chicks?

To solve this problem, we need a basic but useful result.

Theorem 4.2 (Linearity of Expectation)

The expected value of the sum of random variables is equal to the sum of their
expected values.

To solve this problem, we apply Linearity of Expectation. Define ai to be 1 if the

ith chick is not pecked, and otherwise 0. It is easy to see that E(ai ) is equal to the
probability that the ith chick is not pecked, or 14 . Therefore, by Linearity of Expectation,
our answer is just the sum of the ai , which is 25.
This is another example of how a simple theorem can be used to solve nontrivial prob-
lems. To solve even harder problems using Expected value, we need another elementary
theorem.

Theorem 4.3
Given a random variable X with E(X) = n, then with positive probability, the
outcome of X is less than or equal to n, and with positive probability, the outcome
of X is greater than or equal to n.

What is interesting is that this is a very similar result to the Pigeonhole Principle.

4
Amogh Akella — August 2023 How to nuke combo problems, by a combo main

Example 4.4 (Rajiv Gandhi)

Define a Tournament graph to be a directed graph with exactly one edge between
every two vertices. Define a Hamiltonian path to be a path a → b → c . . ., and define
the length of a Hamiltonian path to be the number of vertices in it. Prove that for
every positive integer n, there exists a Tournament graph on n vertices that contains
n!
at least 2n−1 Hamiltonian paths of length n.

Proof. Let G be an arbitrary Tournament graph on n vertices. Let H be an arbitrary tuple

of the n vertices. We say that H describes a Hamiltonian path if H = (h1 , h2 , h3 , . . .) and
h1 → h2 → h3 . . . is a Hamiltonian path. Observe that the probability that H describes
a Hamiltonian path is just the probability that h1 → h2 exists, h2 → h3 exists, and
1
so on. This is equal to just 2n−1 . Because there are n! possible tuples, by Linearity
n!
of Expectation we conclude that the expected value of Hamiltonian paths is just 2n−1 .
By Theorem 4.3, there therefore must exist some graph G that has at least this many
Hamiltonian paths, and the proof is complete.

This proof just shows how powerful Linearity of Expectation is. This method of
choosing a random object is known as the Probabilistic method, which is very useful in
olympiad and non-olympiad problems. We end with one last example:

Example 4.5 (BAMO 2004/4)

Suppose one is given n real numbers, not all zero, but such that their sum is
zero. Prove that one can label these numbers a1 , a2 , . . . an in such a manner that
a1 a2 + a2 a3 + a3 a4 + . . . < 0.

Proof. Suppose that we choose the labels randomly. We will show that the expected
2
value of this sum is strictly negative. This is just equal to n−1 (a1 a2 + a1 a3 + . . .) =
1 2 2 2 1 2 2
n−1 ((a1 + a2 + . . .) − a1 − a 2 − . . .) = n−1 (−a1 − a 2 − . . .) for some positive value C.
However, this is strictly negative, and so by Theorem 4.3, we are done!

Evan Chen has also written another great handout on Expected Value and the Proba-
bilistic Method, you can find it here:
https://web.evanchen.cc/handouts/ProbabilisticMethod/ProbabilisticMethod.pdf

§4.1 Problems for this section

Problem 4.6 (AIME 2006/6). Let S be the set of real numbers that can be represented
as repeating decimals of the form 0.abc where a, b, c are distinct digits. Find the sum of
the elements of S. Hints: 8
Problem 4.7 (IMC 2002 Day 2/2). Two hundred students participated in a mathematical
contest. They had 6 problems to solve. It is known that each problem was correctly
solved by at least 120 participants. Prove that there must be two participants such that
every problem was solved by at least one of these two students. Hints: 9

5
Amogh Akella — August 2023 How to nuke combo problems, by a combo main

§5 Selected Hints
1. Split the circle into some number of sections in such a way that the Pigeonhole
Principle is applicable

2. Find a coloring that B can take advantage of to ensure A cannot win.

3. Consider the n sets of consecutive numbers containing a1 in them.

4. Color the faces formed by the lines black and white.

5. Center a circular section with diameter 2 at the center of the big circle. Split the
rest of the circle evenly into 8 sections.

6. Consider the coloring where one hexagon is colored black, and all hexagons that
are adjacent to two hexagons which are each adjacent to the original hexagon are
colored black, and so on.

7. Color the faces formed by the lines black and white in a checkerboard fashion.

8. Find the expected value of some random element in S.

9. Find the expected value of the number of problems two random contestants both
got wrong.

6
Amogh Akella — August 2023 How to nuke combo problems, by a combo main

References
[1] Evan Chen (2014), Expected Uses of Probability, https://web.evanchen.cc