STEP-BY-STEP LESSON · §9.4
The Pigeonhole Principle
Prove unavoidable repetition using the pigeonhole principle.
Before you begin
Quotient and remainder
For integer n and positive integer d, n=dq+r with integers q,r and 0≤r<d. The remainder bounds select the unique pair, including when n is negative.
Ceiling
⌈x⌉ is the least integer no smaller than real x. For integer c, c=⌈x⌉ exactly when c−1<x≤c. For example, ⌈7/3⌉=3.
Symbols
- ⌈N/k⌉
- the ratio rounded up
- N,k,r
- N≥0 objects; k≥1 boxes; integer capacity r≥0 per box
Definitions and notation for this topic
Floor and ceiling
⌊x⌋; ⌈x⌉
For real x, ⌊x⌋ is the greatest integer ≤x; ⌈x⌉ is the least integer ≥x.
The defining bounds are ⌊x⌋≤x<⌊x⌋+1 and ⌈x⌉−1<x≤⌈x⌉. Floor does not generally mean truncating toward zero.
Separate glossary example
⌊−2.3⌋=−3 and ⌈−2.3⌉=−2; for integer n, both ⌊n⌋ and ⌈n⌉ equal n.
Pigeonhole principle
If N≥0 objects are placed into k≥1 boxes, with N and k integers, at least one box contains at least ⌈N/k⌉ objects.
If every box contained fewer than that threshold, the total capacity would be too small. The expression n+1→n is a mnemonic, not a theorem statement.
Separate glossary example
With 10 objects in 3 boxes, some box contains at least ⌈10/3⌉=4. The familiar n+1 objects in n boxes case gives at least two.
4 people are assigned to 3 rooms.
Step by step
Step 1 / 6
Identify objects and boxes
Objects are what is distributed; boxes are categories. Each object needs exactly one category.
This turns a situation into a precise model.
Worked example
Why must two of 13 people share a birth month?
- Assign each person to exactly one of the 12 month categories.
- There are 12 month categories. Without a match, each holds at most one person.
- There would be at most 12 people, but there are 13. A match is unavoidable.
Optional self-check
Why do 13 objects in four boxes guarantee at least four together, while 12 do not?
Show answer
With at most three per box there are at most 12. Thirteen exceeds this bound; twelve can be placed exactly three per box.