6.2 The Pigeonhole Principle

If you put more objects into boxes than there are boxes, some box must hold at least two. The hard part is choosing what the objects (pigeons) and boxes (holes) are.

The pigeonhole principle

Pigeonhole principle

Let $k \in Z^{+}$ . If $k + 1$ or more objects are placed into $k$ boxes, then at least one box contains two or more objects.

Corollary

A function $f : A \to B$ with $∣ A ∣ > ∣ B ∣$ cannot be one-to-one.

Quick examples from class

367 people: two share a birthday (366 possible birthdays).
27 English words: two end in the same letter (26 letters).
Scores 0–50 (51 possible scores): 52 students guarantee two with the same score.

The generalized pigeonhole principle

Generalized pigeonhole principle

If $N$ objects are placed into $k$ boxes, then some box contains at least $⌈ \frac{N}{k} ⌉$ objects.

Why: if every box had at most $⌈ N / k ⌉ - 1$ objects, the total would be at most $k (⌈ N / k ⌉ - 1) < k (\frac{N}{k} + 1 - 1) = N$ , using $⌈ a ⌉ < a + 1$ . Contradiction.

The two formulas you'll actually use

Guaranteed amount: $N$ objects in $k$ boxes means some box has $\geq ⌈ N / k ⌉$ .
Minimum number needed: to guarantee some box has at least $r$ objects, you need
$N = k (r - 1) + 1.$
Reason: $k (r - 1)$ objects can be spread with exactly $r - 1$ in every box. One more forces a box to reach $r$ .

From class: minimum class size so 5 students get the same grade (10 grades: A, A−, B+, B, B−, C+, C, C−, D, F)

$k = 10$ , $r = 5$ : $N = 10 (4) + 1 = 41$ .

From class: 37 people, months

$⌈ 37/12 ⌉ = 4$ , so at least 4 were born in the same month.

"Specific box" questions: think worst case

Worst-case reasoning

When you need $r$ objects of a specific kind, pigeonhole isn't the right tool. Imagine the worst luck: you draw every other kind first, then $r$ of the kind you want.

From class: cards

At least 3 cards of the same suit (any suit): 4 suits, $r = 3$ , so $4 (2) + 1 = 9$ cards.
At least 3 clubs: in the worst case you draw all 39 non-clubs first, so you need $39 + 3 = 42$ cards.

Writing a pigeonhole proof

Template

Name the pigeons (the objects) and count them: $N$ .
Name the holes (the categories) and count them: $k$ , with $N > k$ .
Say why each pigeon lands in exactly one hole.
Conclude: by the pigeonhole principle, two pigeons share a hole, which means … (translate back into the problem).

Classic hole choices

Problem type	Holes
Two integers with the same remainder mod $d$	the $d$ remainders $0, 1, \dots, d - 1$
Pairs adding to a target (e.g. sum 9 from ${1..8}$ )	the pairs ${1, 8}, {2, 7}, {3, 6}, {4, 5}$
Integer midpoint of lattice points	parity patterns: (even, odd), … ( $2^{dim}$ of them)
Degrees in a network of $n$ computers	possible degrees, of which only $n - 1$ can occur
One integer divides another (from class)	odd parts: write $a = 2^{k} m$ with $m$ odd

From class: among any

n + 1

positive integers not exceeding

2 n

, one divides another

Proof

Write each chosen integer as $a_{j} = 2^{k_{j}} m_{j}$ with $m_{j}$ odd. Each odd part $m_{j}$ is in ${1, 3, 5, \dots, 2 n - 1}$ , which has only $n$ values. With $n + 1$ integers, two have the same odd part: $a_{i} = 2^{k_{i}} m$ and $a_{j} = 2^{k_{j}} m$ . If $k_{i} < k_{j}$ then $a_{i} ∣ a_{j}$ . ∎

From class: every

n

has a multiple whose decimal digits are only 0s and 1s

Proof

Consider the $n + 1$ numbers $1, 11, 111, \dots, n + 1 11 \dots 1$ . There are only $n$ possible remainders mod $n$ , so two of them, say with $i < j$ ones, have the same remainder. Their difference $j - i 1 \dots 1 i 0 \dots 0$ is divisible by $n$ and uses only 0s and 1s. ∎

Computing ceilings without a calculator

$⌈ N / k ⌉$ : divide, and if there's any remainder, round up.

$⌈ 677/38 ⌉$ : $38 \cdot 17 = 646 < 677 \leq 684 = 38 \cdot 18$ , so it is $18$ .
$⌈ 800001/200000 ⌉ = 5$ (because $4 \cdot 200000 = 800000 < 800001$ ).

Common mistakes

Using $N = k r$ instead of $k (r - 1) + 1$ . To guarantee 2 in a box you need $k + 1$ , not $2 k$ .
Forgetting that "at least 3 blue" is a worst-case question, not $⌈ N / k ⌉$ .
In proofs, not saying what the boxes are, or not translating the conclusion back.

Fix to your class notes

"There is a box containing at least ___ objects": the missing word is two.

Exam checklist

Find the minimum $N$ that guarantees $r$ in some box: $k (r - 1) + 1$ .
Find the guaranteed amount $⌈ N / k ⌉$ .
Use worst-case reasoning for a specific category.
Write a clean pigeonhole proof with explicit pigeons and holes (remainders, pairs, parities, degrees).