The Pigeonhole Principle
Use object counts and category capacities to prove that a repeat must exist, without necessarily finding the objects that repeat.
What a learner can do afterwards
- State and apply the pigeonhole principle, its ceiling bound and capacity arguments
- Choose objects and disjoint categories, including complementary pairs and remainder classes
- Build a contradiction proof and explain why two handshake counts must agree
1 · Read
Assign each object to exactly one of n boxes, where n is a positive integer. Boxes may be empty. If objects outnumber boxes, some box contains at least two objects. The counts prove a repeat exists without naming its box. With no more objects than boxes, a repeat may occur, but the counts alone do not force it. Categories can act as boxes: a sock has one colour, and birth months give 12 categories.
For m objects in n boxes, some box contains at least ceiling(m/n) objects. The ceiling is the smallest integer at least m/n. For example, 17 tokens in 5 boxes force at least 4 in some box. This does not mean every box holds 4, or that any box holds exactly 4. To force at least k in one box, the minimum total is n(k-1)+1: n(k-1) objects can be placed with k-1 in each box.
For a contradiction proof, set r = ceiling(m/n). Suppose every box holds at most r-1 objects. Their total is at most n(r-1). But r-1 < m/n, so n(r-1) < m, contradicting the total m. Capacity bounds also work by subtraction. If some boxes together hold at most C of the m objects, the remaining boxes together hold at least m-C.
For n people, with n at least 2, count only handshakes within the group. Nobody shakes their own hand, and each pair shakes at most once. Counts range from 0 to n-1. These endpoints cannot both occur: someone who shook everyone also shook anyone said to have shaken nobody. If 0 occurs, n-1 is absent; otherwise 0 is absent. At most n-1 counts are available for n people, so two counts agree.
To force a sum of 11, partition the integers 1 through 10 into five pairs: (1,10), (2,9), (3,8), (4,7), (5,6). Six distinct selections occupy five pair categories, so one category contains both members. Their sum is 11. Every integer belongs to exactly one pair. Distinctness matters: selecting one member repeatedly need not select its partner.
Division by a positive integer d gives d remainder categories: 0 through d-1. Equal remainders give a divisible difference. Write a = du+r and b = dv+r; then a-b = d(u-v), a multiple of d. Thus d+1 selected integers force two whose difference is divisible by d. The d integers 0 through d-1 have different remainders, showing that d selections need not suffice.
The ceiling bound is sharp. Write m = qn+s, where q and s are integers and 0 <= s < n. Put q+1 objects in s boxes and q in the other n-s boxes. This places s(q+1)+(n-s)q = m objects. If s=0, every box holds q = ceiling(m/n). If s>0, the largest occupancy is q+1 = ceiling(m/n). No larger lower bound works for every placement.
For 17 = 3 times 5 + 2, two boxes hold 4 and three hold 3. This placement shows that a guarantee of 5 would be too large.
Assign each object to one category. Compare counts or capacities. A guarantee concerns every allowed placement, even when the proof does not identify the repeated objects.
Lesson, practice questions, worked solutions and flashcards written for this dataset.
Additional readings, questions, worked solutions and flashcards written for this dataset.
More to read
Check the assignment
A pigeonhole proof needs a category for every object. No object may be omitted or assigned to several categories. Empty categories are allowed.
Suppose a collection has more objects than categories. If each category contained at most one object, there would be at most as many objects as categories. That contradicts the given counts, so a category must contain two objects.
The conclusion does not identify the repeated objects. It also requires no random experiment or equal chances. It holds for every assignment satisfying the conditions.
If the objects do not outnumber the categories, the counts alone do not force a repeat. A placement with one object per category may avoid it. Another placement may contain a repeat. Check the difference between an outcome that can happen and one that must happen.
Prove a bound and test its limit
For m objects in n boxes, where m is a nonnegative integer and n is a positive integer, some box holds at least ceiling(m/n) objects. This says at least, not exactly. It concerns some box, not every box.
To force k objects in one box, first calculate how many fit if every box is limited to k-1. The total capacity is n(k-1). One more object forces the desired occupancy. The placement with k-1 per box shows why a smaller total does not guarantee it.
The ceiling bound itself can also be attained. Divide m by n to get m=qn+s, with 0<=s<n. Give every box q objects, then give one extra to each of s boxes. The largest count equals ceiling(m/n), so a larger universal lower bound is impossible.
For boxes with known limits, add their capacities. Subtract that sum from the total to bound how many objects must remain elsewhere.
Choose categories that imply the result
A repeated category is useful when sharing that category gives the relation you want.
For a fixed target sum, complementary pairs can form the categories. More distinct selected numbers than pairs force a category containing both members. Repeated values do not support that last step: two copies of one member need not include its partner.
For a divisible difference, use remainder categories. Two integers with remainder r on division by d have forms du+r and dv+r. Subtracting gives d(u-v), so their difference is divisible by d.
Handshake counts need an exclusion before counting categories. In a group of n people, where n is at least 2, count only handshakes within the group, with none to oneself and at most one per pair. Counts lie from 0 to n-1. A person who shook everyone cannot coexist with someone who shook nobody. At most n-1 count categories can therefore occur among n people, forcing equal counts.
2 · Watch
Take it off screen
Where it sits
Learn first
Optional connections
This opens up
18 questions wait behind this lesson, each with its answer explained. Every answer feeds the sky: stars light as they are learned, and dim when it is time to come back.