How to spot a pigeonhole problem in under a minute

Nobody fails a pigeonhole problem because they do not understand pigeonhole. The statement fits on one line, and a ten-year-old gets it immediately: put more objects than boxes, and some box holds two.

People fail pigeonhole problems because they do not recognise them. In a contest you get a paragraph about points in a square, or divisors, or people at a party, and nothing in it says "boxes". The whole difficulty is upstream of the technique: it is knowing that this is where the technique goes.

So this is not an explanation of the pigeonhole principle. It is a recognition drill.

The four signals

Almost every pigeonhole problem you will meet on an AMC or an olympiad paper announces itself in one of four ways. Learn the phrasing, not the theory.

• "Among any n …, two must …": the single most reliable tell there is. The words any and two together are pigeonhole in almost every case. Among any 13 people, two share a birth month is the archetype: 13 objects, 12 boxes, done.
• A count that is suspiciously close to another count. If a problem hands you 13 of something and 12 of something else, or $n+1$ from a set of size $2n$, the near-miss is not decoration. Someone chose those numbers so that one exceeds the other by exactly one.
• "Show that two of them are within / differ by / share …": a relationship between two unnamed members of a set. You are not asked which two. That anonymity is the signature: pigeonhole proves a pair exists without ever finding it.
• A continuous region with a size attached. Points in a square, in a triangle, on a segment. The boxes will be a subdivision of the region, and the bound you are asked for is the diameter of one piece.

The three questions that turn a signal into a proof

Recognition gets you to the technique. These get you through it. Ask them in order, and write the answers down before you write anything else.

1. What are the pigeons? Name the objects being distributed, and count them exactly. Not "the points". The 5 points.
2. What are the boxes? This is the entire problem. Everything else is bookkeeping. The boxes are almost never given to you; you invent them, and inventing them well is the skill.
3. Why does two in a box finish it? If you cannot say what a collision gives you, you have the wrong boxes. Go back to question 2.

Question 3 is the one people skip, and skipping it is why a promising attempt dies halfway. You should be able to finish the sentence "if two land in the same box then …" before you start proving anything.

Watching it work

Take any 5 points inside a unit square, two within distance $\tfrac{\sqrt2}{2}$. Signal four fires: a region, a count, a distance.

Pigeons: the 5 points. Boxes: cut the unit square into four quarters of side $\tfrac12$. Five points, four quarters, so some quarter holds two. And two points inside a square of side $\tfrac12$ are at most its diagonal apart, $\sqrt{(1/2)^2 + (1/2)^2} = \tfrac{\sqrt2}{2}$. Question 3 answers itself, which is how you know the boxes were right.

Notice what the bound in the problem did: it told you the box size. The number $\tfrac{\sqrt2}{2}$ is a diagonal, and a diagonal of $\tfrac{\sqrt2}{2}$ means a square of side $\tfrac12$, which means four boxes. The answer was reverse-engineered from the thing you were asked to prove. That trick generalises further than almost anything else here: when a problem hands you a specific constant, try to read the box off it.

When the boxes are not obvious

The four signals get you to pigeonhole. They do not hand you question 2, and on harder problems the boxes are genuinely hidden.

Among any $n+1$ numbers chosen from $\{1, 2, \dots, 2n\}$, one divides another is the standard example. There is no region to cut and no calendar to use. The boxes turn out to be odd parts: write each chosen number as $2^k \cdot m$ with $m$ odd. There are only $n$ odd numbers in the range, you chose $n+1$ numbers, so two share an odd part, and of those two, the one with the smaller power of 2 divides the other.

The move worth stealing is not the odd part. It is that the boxes were built by throwing information away. Every number got crushed down to a single feature, and the crushing is what made the boxes scarce enough to collide. When a pigeonhole problem has no visible boxes, ask what you could forget about each object while keeping what the conclusion needs.

The same shape runs through the six-person party problem, where the boxes are the two colours on the five edges at a single vertex. Three of them must match, and that trio is where the monochromatic triangle comes from.

What to do with this

The recognition skill is trained by volume, not by reading. Take twenty combinatorics problems, and for each one write only three lines: pigeons, boxes, why a collision finishes it. Do not solve them. You will get through twenty in the time one full solution takes, and the pattern-matching is what you are actually short of.

Lemma teaches this as a named technique rather than as a trick you meet twice. The pigeonhole principle page has the statement, the generalisation to $\lceil n/k \rceil$, and where it sits in the ladder. The problem archive has the statements above in full, with difficulty and expected time on each. And the daily problem posts a new one every day in three tiers, no account needed, which is a cheap way to keep the recognition muscle warm between sessions.