Pigeonhole & Extremal

Study Sheet

Pigeonhole & Extremal

Existence from counting and extremes

Two Existence Principles

Tip
Pigeonhole principle

If n+1n+1 objects go into nn boxes, some box holds at least two; more generally some box holds at least m/n\lceil m/n\rceil of mm objects.

In plain terms. More items than boxes forces a box to double up. The trick is choosing boxes so that "two in a box" is exactly what you want.

Example. Among any 1313 people, two share a birth month: 1313 people, 1212 months, so some month repeats.

Tip
Extremal principle

Consider the largest, smallest, or closest object; its extremal property forces structure.

In plain terms. Look at the most extreme case in the setup — the biggest, smallest, or nearest — and its special status usually breaks the problem open.

Example. Among finitely many points, the two closest ones can't have a third point strictly between them.