1
It is “Injective, Surjective, Bijective” restated
No injection exists from a larger finite set to a smaller one. Objects are the domain, boxes the codomain, and a collision is two objects sharing a box.
Lesson · Sets, Relations, and Functions · Counting
The Pigeonhole Principle
If n objects go into k boxes with n > k, some box holds at least two. It is obvious, it is a one-line consequence of “Injective, Surjective, Bijective”, and it proves things that are not obvious at all.
n objects, k boxes, n > k ⟹ some box has ≥ 2
generalised: some box has ≥ ⌈n/k⌉
equivalently: no injection A → B when |A| > |B|
The art is choosing the boxes.
The principle, and its sharpening
Core ideas
What this lesson establishes
The statement is trivial. Every application is an act of choosing what the boxes are, and that is where the work is.
2
The generalised form is sharper
With n objects in k boxes some box holds at least ⌈n/k⌉. The basic form is this with n = k + 1.
3
Choosing the boxes is the whole difficulty
The principle never tells you what the boxes are. Every interesting application is a clever choice of classification.
The material
The principle and its applications
Statement, proof, and four uses of increasing subtlety.
Theorem · Pigeonhole principle
If n objects are placed into k boxes and n > k, then some box contains at least two objects.
Suppose every box contained at most one object. Then the total number of objects would be at most k, contradicting n > k.
□
Theorem · Generalised pigeonhole principle
If n objects are placed into k boxes, some box contains at least ⌈n/k⌉ objects.
Suppose every box held at most ⌈n/k⌉ − 1 objects. The total would then be at most k(⌈n/k⌉ − 1). Since ⌈n/k⌉ < n/k + 1, this is less than k(n/k + 1 − 1) = n, contradicting that all n objects were placed.
□
Four applications
Example · Shared birthdays
Among 367 people, two share a birthday. Boxes are the 366 possible dates; objects are the people. No assumption about distribution is needed — this is certainty, not probability, and is a different claim from the birthday problem of Discrete Probability.
Example · A repeated remainder
Among any n + 1 integers, two leave the same remainder on division by n. The boxes are the n possible remainders 0, …, n−1. Consequently their difference is divisible by n, which is a fact about divisibility obtained by counting.
Example · Two people with the same number of friends
In any group of n ≥ 2 people, two have the same number of acquaintances within the group. Degrees range over 0, …, n−1 — n boxes for n people, which is not enough on its own. But 0 and n−1 cannot both occur: if someone knows nobody, nobody can know everybody. So only n−1 boxes are actually available, and the principle applies.
That third example is the one worth studying. A naive count gives exactly as many boxes as objects, and the principle does not apply; the argument that two boxes are mutually exclusive is what creates the surplus. Applications usually turn on an observation of that kind.
Example · A subset summing to a multiple of n
Given any n integers a₁, …, aₙ, some consecutive block aᵢ₊₁ + ⋯ + aⱼ is divisible by n. Consider the n partial sums s₁, …, sₙ and their remainders mod n. If some sⱼ ≡ 0 we are done; otherwise the n remainders lie in the n−1 boxes 1, …, n−1, so two partial sums share a remainder, and their difference — a consecutive block — is divisible by n.
None of these is a statement about counting on its face, and every one is proved by counting. That is the pattern: the principle converts a size comparison into an existence claim, and the existence claim is what you actually wanted.
Interactive
Injective, surjective, bijective
Built by hand, classified by counting
Method
Applying the principle
The objects are usually given. The boxes are yours to invent.
1
Identify the objects
Usually stated in the problem: the people, the integers, the points. This step is rarely the difficulty.
2
Invent the boxes
A classification with fewer categories than objects. Remainders, parities, ranges, and degree counts are the standard choices.
3
Count both sides
You need strictly more objects than boxes. If the counts are equal, look for a reason some box is unusable — that was the friends argument.
4
Say what a shared box means
Two objects in one box gives you the conclusion: same remainder means the difference divides, same degree means the claim is proved. Name it.
Pigeonhole
Score 0 / 0Choose the answer you can justify.
Five points in a unit square
Show two of any five points are within √2 / 2 of each other.
Boxes: cut the unit square into four quarters, each ½ × ½.
Objects: the five points.
5 points into 4 quarters ⟹ some quarter holds two points.
Two points in a ½ × ½ square are at most its diagonal apart:
√(½² + ½²) = √(1/2) = √2 / 2 ≈ 0.707
So two of the five points are within √2 / 2 of each other. ∎
The choice of four quarters is the entire proof. Cutting into nine ninths would give nine boxes for five points and prove nothing; cutting into two halves would give a weaker bound. The classification is chosen to make the counts work and the conclusion strong.
Common mistakes
1
Choosing boxes that outnumber the objectsThe principle needs strictly more objects than boxes. A finer classification is not a better one.
2
Rounding the generalised bound downIt is ⌈n/k⌉. With 20 objects and 6 boxes the guarantee is 4, not 3.
3
Reading the conclusion as probabilisticPigeonhole gives certainty. "Two of 367 people share a birthday" is not likely; it is unavoidable, and Discrete Probability's birthday problem is a genuinely different question.
Check your understanding
✓
Finish when you can invent the boxes yourself.
Prove that among any 10 distinct integers between 1 and 100, two different subsets have the same sum. The objects are subsets and the boxes are possible sums — count both and the argument writes itself, which is the skill this lesson is for.
Note: “The Generalised Pigeonhole Principle” in Combinatorics and Counting returns to the generalised principle with harder applications, and Graphs and Trees uses it to prove that a graph on n vertices with more than n − 1 edges must contain a cycle. It is the most reusable single fact on this path.