Pigeonhole Arguments

Prove that among any 13 people, at least two share a birth month. That one's easy by inspection — 12 months, 13 people, someone doubles up. Now the real question: in any group of 6 people at a party, either at least 3 of them are mutual friends, or at least 3 of them are mutual strangers (assume friendship is symmetric — either two people know each other or they don't). Prove it. This one doesn't have an obvious "container" to count, and yet it's the same principle in disguise.

Try the second one before reading on — pick one person and think about their 5 relationships to everyone else.

The trap: looking for an explicit construction

Both statements are existence claims — "at least two must," "at least three must" — and existence claims often tempt people to try to build an example that satisfies the conclusion, which is both harder than necessary and the wrong tool. The pigeonhole principle proves existence without construction: it just counts, and shows that avoiding the conclusion is numerically impossible.

Worked example: 13 people, 12 months — the container is obvious

Pigeons: the 13 people. Holes: the 12 possible birth months. Since $13 > 12$, at least one hole (month) contains at least $\lceil 13/12 \rceil = 2$ pigeons — two people share that month. This case is included only to fix the vocabulary; the interesting cases hide the containers.

Worked example: 6 people, friends or strangers — the container is hidden

Pick any one person, call them A. A has exactly 5 relationships, one to each other person, and each relationship is either "friend" or "stranger" — two categories. By pigeonhole, among A's 5 relationships, at least $\lceil 5/2 \rceil = 3$ fall into the same category. Say (WLOG — the stranger case is symmetric) that A has at least 3 friends: call them $B, C, D$.

Now look only at the relationships among $B, C, D$ themselves. If any pair among them — say $B$ and $C$ — are friends, then $A, B, C$ are all mutual friends (A is friends with both by construction, and B, C are friends with each other): a mutual-friend triple, done. If instead no pair among $B, C, D$ is friends — i.e. $B,C,D$ are pairwise strangers — then $B, C, D$ themselves form a mutual-stranger triple, done.

Either way, a triple of the required kind exists. The pigeons in the second application were the 3 pairs among $\{B,C,D\}$, and the holes were "friend" or "stranger" — but really the whole proof is pigeonhole applied twice, once to find 3 people related the same way to $A$, once to check the relationships among those 3.

$$\left\lceil \frac{5}{2} \right\rceil = 3.$$

In words: five relationships split two ways always leaves one side with at least three — that single ceiling-division is the entire engine of the proof.

A second flavour: the generalised (ceiling) version, worked with numbers

A drawer has socks of 4 colours. How many socks must you pull, blindly, to guarantee a matching pair? Pigeons: the socks you pull. Holes: the 4 colours. You want the smallest $n$ forcing $\lceil n/4\rceil \ge 2$, i.e. some colour hits 2. The largest $n$ that can still avoid a repeat is $n=4$ (one of each colour, zero matches) — so pulling $n=5$ forces $\lceil 5/4\rceil = 2$, a guaranteed match. The general rule: to force $m$ items in one hole among $k$ holes, you need $n = k(m-1)+1$ pigeons — here $k=4, m=2$: $4(1)+1=5$, matching the hand count exactly.

The transferable technique

Whenever a puzzle claims something must exist — a repeat, a monochromatic structure, a bound on how spread out something can be — ask two questions: what are the pigeons (the things being distributed), and what are the holes (the categories they're forced into)? The holes are rarely announced explicitly; finding them, often by fixing one element of the problem and looking at its relationships to everything else (as with person A above), is the actual creative step. Once the pigeons and holes are named, the arithmetic — a single ceiling-division — finishes the proof.