Greedy arguments in olympiad combinatorics: when they work

Greedy is the first idea anyone has on a construction problem: take the best available move, then the next best, and hope. It is also the idea most often written up and marked zero, because the write-up proves nothing. The algorithm was never the hard part. The hard part is knowing whether greedy actually works here, and then saying why in a way a marker can check.

So this is not a description of greedy algorithms. It is a guide to recognising when a greedy argument is available, and to the two sentences every greedy proof owes.

The signals

Greedy is worth trying when the problem has some of these features. None is decisive alone, but two together are a strong hint.

• "Show that it is always possible to …" An existence claim about an arrangement, an ordering or a schedule. You are allowed to build the object, and building it one piece at a time is the most natural way to build anything.
• "Find the largest (or smallest) number of …" An optimisation over a finite set of choices, where each choice is small and they are made in sequence.
• Pieces that only interact locally. Adding one element only has to agree with the elements already placed, not with the whole future. That locality is what makes a step-by-step construction possible at all.
• A natural order. Sizes, times, positions on a line. If the objects can be sorted by something, greedy is usually "process them in that order".

The two obligations

Every algorithmic or greedy argument has two halves, and a write-up that merges them usually proves only one.

1. The step is always available. At every stage the greedy move exists: the procedure never gets stuck. For an existence problem this is often the entire difficulty.
2. The result is correct. When the procedure ends, the thing it built has the required property, or for an optimisation problem, nothing does better. The standard tool here is the exchange argument: take any optimal answer and show you can swap its choices for greedy's, one at a time, without making it worse.

If you cannot say which of the two your problem is really about, you are not ready to write.

Watching it work: never getting stuck

Every tournament has a path through all the players, each beating the next. Build it greedily: order the players one at a time, inserting each new player somewhere in the path already built.

Obligation 2 is free. Inserting a player between two neighbours they fit between keeps the path a path. So the whole problem is obligation 1: is there always somewhere to put the new player?

Read along the existing path and write W where the new player beats that person and L where they lose. If the first letter is W, put them at the front. If the last letter is L, put them at the back. Otherwise the string starts with L and ends with W, so somewhere an L is immediately followed by a W, and the new player slots in exactly there: beaten by the person before, beating the person after.

That is a discrete intermediate value argument, and it is the most common way obligation 1 gets discharged. Notice that the greedy step here is "insert anywhere that works", not "insert at the best place". Greedy does not have to mean optimising. It means committing to each piece and never going back.

When greedy is simply wrong

Two standard examples, both worth carrying around as reflexes.

Making change. With coins worth $1$, $3$ and $4$, pay $6$. Greedy takes the largest coin that fits, so $4 + 1 + 1$, three coins. But $3 + 3$ is two. With the coins $1$, $5$, $10$ and $25$ greedy happens to be optimal for every amount, but that is a fact about those particular coins, and it has to be proved for them. It is not a property of greedy.

Scheduling. You have talks with start and end times and want to attend as many as possible without overlap. There are three natural greedy rules, and only one works.

• Shortest talk first fails: talks at $[0, 5)$, $[4, 7)$, $[6, 10)$. The shortest one overlaps both others, so greedy attends one talk where two were possible.
• Earliest start first fails: $[0, 10)$, $[1, 2)$, $[3, 4)$. The early starter blocks everything.
• Earliest finish first works, and the exchange argument says why. Take any optimal schedule. Its first talk ends no earlier than greedy's first choice, so swap it for greedy's choice: nothing else in the schedule is disturbed, because greedy's talk ends sooner. Repeat on what is left. The optimal schedule becomes greedy's without ever losing a talk.

The shape of the exchange argument is worth memorising, because it transfers: greedy's first choice is at least as good as the optimum's first choice, and choosing it leaves at least as much room for the rest. If you can prove both halves of that sentence for your rule, you have a proof.

Greedy as a proof tool

The most useful greedy arguments in olympiad combinatorics are not algorithms anyone wants to run. They are procedures you describe only so that you can count what they produce.

Take the Erdős–Szekeres theorem: any sequence of $mn + 1$ distinct reals has an increasing subsequence of length $m + 1$ or a decreasing one of length $n + 1$. Here is a greedy proof. Deal the numbers into piles, left to right in the order they appear: each number goes on top of the leftmost pile whose top is larger than it, or starts a new pile on the right if there is none.

Two facts about this procedure, and they are the two obligations in disguise:

• Every pile is decreasing, read bottom to top. A number only goes on a pile whose top is bigger. So two members of an increasing subsequence can never share a pile, and there are at least as many piles as the longest increasing subsequence is long.
• There are exactly that many piles. When a number lands on pile $k$, the top of pile $k - 1$ at that moment is smaller than it, otherwise it would have gone further left. Following those links back from any number on the last pile spells out an increasing subsequence with one term from every pile.

Now finish with pigeonhole. If no increasing subsequence has length $m + 1$, there are at most $m$ piles. There are $mn + 1$ numbers, so some pile holds at least $n + 1$ of them, and that pile is a decreasing subsequence.

The bound is exact, which is worth checking rather than assuming: $7, 8, 9, 4, 5, 6, 1, 2, 3$ has $mn = 9$ terms for $m = n = 3$, and its longest increasing and decreasing subsequences both have length $3$.

The archive's solution to that problem uses a different argument, labelling each term with a pair of numbers. Knowing two proofs of the same statement is not redundancy. It is how you find out which idea the problem was really about.

What to practise

Take ten "show it is always possible" or "find the maximum" combinatorics problems. For each one, write down a greedy rule, try to break it on a tiny example, and if it survives, write one line for each obligation: why the step is always available, and why the result is right. Do not write full solutions. Deciding whether greedy is viable, in two minutes, is the skill a timed paper actually rewards.

Lemma teaches algorithmic and greedy constructions as a named technique, alongside the monovariant arguments that prove a procedure stops. The problem archive has both problems above in full, each with a marking rubric. And the daily problem posts a new one every day at three difficulties, no account needed.