The Central Idea
Suppose \(n+1\) objects are placed into \(n\) boxes.
Then at least one box must contain at least two objects.
Symbolically,
\[ \boxed{n+1\text{ objects in }n\text{ boxes} \Longrightarrow \text{some box contains at least }2\text{ objects}.} \]The objects are traditionally called pigeons, and the boxes are called pigeonholes.
A First Example
Suppose \(13\) people are grouped according to their birth month.
There are only \(12\) possible months.
Therefore, at least two of the \(13\) people must share a birth month.
We do not know which month is shared, but we know that some shared month must exist.
The Principle Proves Existence
The pigeonhole principle is often used to prove that something must exist.
It may not identify the exact objects involved.
Instead, it proves that avoiding the claimed situation is impossible.
Objects and Categories
The main skill is deciding what should play the roles of pigeons and pigeonholes.
Typical pigeons include:
- people;
- numbers;
- files;
- points;
- messages;
- states;
- sequences.
Typical pigeonholes include:
- months;
- remainders;
- categories;
- intervals;
- locations;
- possible values;
- equivalence classes.
Example: Same Remainder
Choose \(6\) integers.
When divided by \(5\), every integer has one of the remainders
\[ 0,1,2,3,4. \]There are \(5\) possible remainder classes but \(6\) integers.
Therefore, at least two of the integers must have the same remainder modulo \(5\).
Why the Basic Principle Is True
Suppose, for contradiction, that \(n+1\) objects are placed into \(n\) boxes and no box contains more than one object.
Then the total number of objects could be at most
\[ n. \]But we have
\[ n+1 \]objects.
This is impossible.
Therefore, some box must contain at least two objects.
The Generalized Pigeonhole Principle
The principle extends beyond forcing a pair.
If \(N\) objects are distributed among \(k\) boxes, then some box contains at least
\[ \boxed{\left\lceil\frac{N}{k}\right\rceil} \]objects.
Here, \(\lceil x\rceil\) means the least integer greater than or equal to \(x\).
Why the Ceiling Appears
The average number of objects per box is
\[ \frac{N}{k}. \]At least one box must contain at least the ceiling of this average.
For example, if \(17\) objects are placed into \(5\) boxes, then
\[ \frac{17}{5}=3.4. \]Since a box cannot contain \(3.4\) objects, some box must contain at least
\[ \boxed{\left\lceil3.4\right\rceil=4} \]objects.
Example: Students in Classes
Suppose \(103\) students are divided among \(8\) class sections.
Then some section contains at least
\[ \left\lceil\frac{103}{8}\right\rceil = \left\lceil12.875\right\rceil = 13 \]students.
Therefore,
\[ \boxed{\text{some class has at least }13\text{ students}.} \]A Threshold Form
Another useful form asks how many objects are needed to guarantee that some box receives at least \(r\) objects.
If every box had at most \(r-1\) objects, then \(k\) boxes could contain at most
\[ k(r-1) \]objects.
Therefore,
\[ \boxed{k(r-1)+1} \]objects guarantee that some box contains at least \(r\) objects.
Example: Guaranteeing Three in One Month
How many people are needed to guarantee that at least \(3\) share a birth month?
There are \(12\) months.
If every month contained at most \(2\) people, then there could be at most
\[ 12\cdot2=24 \]people.
One more person forces some month to contain at least \(3\):
\[ \boxed{25}. \]Example: Guaranteeing Five in One Category
Suppose objects are classified into \(7\) categories.
To guarantee that some category contains at least \(5\) objects, we need
\[ 7(5-1)+1. \]Therefore,
\[ \boxed{29} \]objects are sufficient.
Maximum without Forcing a Collision
The basic pigeonhole principle can also be read in reverse.
If there are \(k\) boxes and we want to avoid putting two objects in the same box, then we can place at most
\[ \boxed{k} \]objects.
The next object forces a collision.
Maximum without Forcing \(r\) in One Box
To avoid having \(r\) objects in any box, each box may contain at most
\[ r-1 \]objects.
With \(k\) boxes, the largest possible total is
\[ \boxed{k(r-1)}. \]This upper-bound viewpoint is often the fastest route to a pigeonhole proof.
Example: Same Last Digit
Choose \(11\) integers.
Every integer has one of \(10\) possible last digits:
\[ 0,1,2,\ldots,9. \]Since there are \(11\) integers but only \(10\) last-digit categories, at least two chosen integers must have the same last digit.
Example: Same Remainder Modulo \(n\)
If \(n+1\) integers are selected, then at least two have the same remainder when divided by \(n\).
There are only
\[ n \]residue classes modulo \(n\):
\[ 0,1,\ldots,n-1. \]Thus the \(n+1\) integers are the pigeons and the \(n\) residue classes are the pigeonholes.
A Consequence for Differences
If two integers have the same remainder modulo \(n\), then their difference is divisible by \(n\).
Therefore, among any \(n+1\) integers, there exist two whose difference is a multiple of \(n\).
Example: A Difference Divisible by 7
Choose any \(8\) integers.
There are only \(7\) possible remainders modulo \(7\).
Therefore, two selected integers share a remainder modulo \(7\).
Their difference is divisible by
\[ \boxed{7}. \]Geometric Pigeonholes
Pigeonholes do not need to be literal boxes or named categories.
A geometric region can be divided into smaller subregions, with each subregion acting as a pigeonhole.
If enough points are placed in the larger region, some smaller subregion must contain several points.
Example: Points in a Square
Divide a square into \(4\) smaller squares.
Place \(5\) points anywhere in the original square.
Since there are \(5\) points and only \(4\) smaller squares, at least one smaller square contains at least two points.
Intervals as Pigeonholes
Suppose the interval
\[ [0,1] \]is divided into \(10\) equal subintervals.
If \(11\) points are chosen in a way that assigns each point to one of those subintervals, then some subinterval contains at least two chosen points.
This type of argument can produce guarantees about distance and proximity.
Functions and the Pigeonhole Principle
Suppose a function maps a finite set \(A\) into a finite set \(B\).
If
\[ |A|>|B|, \]then the function cannot be injective.
At least two elements of \(A\) must map to the same element of \(B\).
Why a Larger Domain Forces a Collision
Treat the domain elements as pigeons and the codomain elements as pigeonholes.
If there are more domain elements than possible outputs, then at least two inputs must share an output.
Thus,
\[ \boxed{|A|>|B|\Longrightarrow \text{no function }A\to B\text{ can be injective}.} \]A Finite Injective-Surjective Connection
If finite sets \(A\) and \(B\) have the same size and a function
\[ f:A\to B \]is injective, then it must also be surjective.
Otherwise, some element of \(B\) would remain unused, leaving fewer than \(|A|\) available outputs for \(|A|\) distinct inputs.
The pigeonhole principle makes this finite counting fact natural.
Repeated States
Suppose a process can occupy only \(m\) possible states.
If we observe
\[ m+1 \]states in the process, then at least one state must appear at least twice.
This observation is important in finite-state systems, algorithms, and repeated processes.
Example: Finite Machine States
A machine has \(20\) possible internal states.
If its state is recorded at \(21\) different times, then at least two records must show the same state.
The statement does not say that the machine necessarily repeats its entire future behavior, but it guarantees a repeated recorded state.
Sequences and Repeated Values
Suppose a sequence has \(N\) terms but each term can take only \(k\) possible values.
Then some value appears at least
\[ \boxed{\left\lceil\frac{N}{k}\right\rceil} \]times.
Example: Repeated Grades
Suppose \(31\) assignments receive one of \(5\) letter grades:
\[ A,\ B,\ C,\ D,\ F. \]Then some grade must occur at least
\[ \left\lceil\frac{31}{5}\right\rceil = 7 \]times.
Therefore,
\[ \boxed{\text{some grade occurs at least }7\text{ times}.} \]The Average-Load Viewpoint
The generalized principle can be interpreted as a load-balancing statement.
If \(N\) items are distributed among \(k\) containers, the average load is
\[ \frac{N}{k}. \]At least one container must have load at least the ceiling of the average.
Similarly, at least one container has load no greater than the floor of the average.
Contrapositive Form
Sometimes it is useful to state the generalized pigeonhole principle as an upper bound.
If every one of \(k\) boxes contains at most \(r\) objects, then the total number of objects is at most
\[ \boxed{kr}. \]Therefore, any total greater than \(kr\) forces some box to contain at least \(r+1\) objects.
Example: Files on Servers
Suppose \(1001\) files are distributed among \(10\) servers.
Then some server contains at least
\[ \left\lceil\frac{1001}{10}\right\rceil = 101 \]files.
If every server contained at most \(100\) files, the system could store at most
\[ 10\cdot100=1000 \]files, which is not enough.
The Principle Does Not Require Equal Distribution
The pigeonhole principle does not assume that objects are distributed evenly.
The actual distribution may be highly uneven.
The principle gives a guaranteed minimum for the most crowded box regardless of how the objects are distributed.
The Guarantee May Not Be Stronger Than Necessary
The generalized bound
\[ \left\lceil\frac{N}{k}\right\rceil \]is the strongest universal guarantee obtainable from the counts \(N\) and \(k\) alone.
Additional structure may allow a stronger conclusion, but that requires more information than the pigeonhole counts by themselves provide.
Sharpness of the Bound
Suppose
\[ N=qk+r \]
with \(0\le r
The objects can often be distributed so that some boxes contain \(q+1\)
objects and the rest contain \(q\).
This shows why the guaranteed maximum load is exactly
Example: Why 13 Is Best Possible
With \(103\) students in \(8\) classes, the principle guarantees a class with at least \(13\) students.
This cannot be improved to \(14\) from the total count alone, because a distribution such as
\[ 13,13,13,13,13,13,13,12 \]contains \(103\) students but no class has \(14\).
Finding the Pigeonholes Is the Main Creative Step
In simple examples, the pigeonholes are obvious.
In stronger applications, the real work is choosing categories that force the conclusion we want.
A useful question is:
What classification would make two objects in the same category give me the desired result?
Example: Equal Remainders Create Divisible Differences
Suppose the desired conclusion is that two selected integers differ by a multiple of \(9\).
Classify each integer by its remainder modulo \(9\).
Two integers in the same pigeonhole have equal remainders, so their difference is divisible by \(9\).
Thus, \(10\) selected integers are enough to force the desired pair.
Common Error: Counting the Wrong Pigeonholes
The categories must match the property being forced.
If we want equal remainders modulo \(7\), then there are \(7\) pigeonholes, not \(8\) and not \(6\).
The pigeonholes are the remainder classes
\[ 0,1,2,3,4,5,6. \]Common Error: Forgetting the Ceiling
If \(22\) objects are placed into \(6\) boxes, then
\[ \frac{22}{6}\approx3.67. \]The principle guarantees at least
\[ \boxed{4} \]objects in some box, not \(3.67\) and not \(3\).
Common Error: Claiming More Than the Principle Guarantees
If \(13\) people are classified by \(12\) birth months, the principle guarantees that some two share a month.
It does not guarantee that three people share a month.
To guarantee three in one month, \(25\) people are needed.
Common Error: Assuming Every Box Must Be Crowded
The conclusion is existential:
\[ \text{some box} \]must meet the bound.
The principle does not say that every box contains that many objects.
Common Error: Confusing Average with Guarantee
If the average load is
\[ 4.2, \]we may conclude that some box contains at least \(5\) objects.
We cannot conclude that every box contains \(4\) or \(5\) objects.
The distribution may be very uneven.
A Reliable Procedure
- Identify the objects being distributed.
- Identify the categories or pigeonholes.
- Count the number \(N\) of objects.
- Count the number \(k\) of pigeonholes.
- Use \(\lceil N/k\rceil\) for the generalized guarantee.
- For a target of \(r\) objects in one box, use \(k(r-1)+1\).
- Translate the crowded pigeonhole back into the original context.
- Check that the chosen categories actually imply the desired conclusion.
Example: Full Workflow
Show that among any \(15\) integers, at least two have the same remainder when divided by \(14\).
Pigeons:
\[ 15\text{ integers}. \]Pigeonholes:
\[ 14\text{ remainder classes modulo }14. \]Since
\[ 15>14, \]at least two integers occupy the same remainder class.
Therefore,
\[ \boxed{\text{two of the integers have the same remainder modulo }14.} \]Practice 1: Birth Months
How many people are needed to guarantee that at least two share a birth month?
Practice 2: Generalized Principle
If \(41\) objects are placed into \(6\) boxes, what is the minimum number of objects guaranteed to be in some box?
Practice 3: Same Remainder
How many integers must be chosen to guarantee that two have the same remainder modulo \(8\)?
Practice 4: Guaranteeing Four
How many objects must be placed into \(9\) boxes to guarantee that some box contains at least \(4\) objects?
Practice 5: Letter Grades
If \(27\) assignments receive one of \(5\) possible letter grades, what is the minimum number of assignments that must receive the same grade?
Practice 6: Last Digits
Show that among any \(11\) integers, at least two have the same last digit.
Practice 7: Functions
Can a function from a \(12\)-element set to a \(9\)-element set be injective? Explain.
Practice 8: Server Load
If \(250\) files are distributed among \(12\) servers, how many files are guaranteed to be on at least one server?
Practice 9: Three Shared Months
How many people are needed to guarantee that at least \(4\) people share a birth month?
Practice 10: Identify the Error
A student says that placing \(20\) objects into \(6\) boxes guarantees some box contains at least
\[ \left\lfloor\frac{20}{6}\right\rfloor=3 \]objects. What stronger conclusion follows?
Practice Answers
Practice 1
There are \(12\) months, so one more person than months guarantees a repeat:
\[ \boxed{13}. \]Practice 2
\[ \left\lceil\frac{41}{6}\right\rceil = \left\lceil6.833\ldots\right\rceil = \boxed{7}. \]Practice 3
There are \(8\) remainder classes modulo \(8\), so
\[ \boxed{9} \]integers guarantee a shared remainder.
Practice 4
To avoid \(4\) in a box, each box may contain at most \(3\):
\[ 9\cdot3=27. \]Therefore,
\[ \boxed{28} \]objects guarantee at least \(4\) in one box.
Practice 5
\[ \left\lceil\frac{27}{5}\right\rceil = \boxed{6}. \]Practice 6
There are only \(10\) possible last digits but \(11\) integers. By the pigeonhole principle, at least two integers share a last digit.
Practice 7
No. There are \(12\) domain elements but only \(9\) possible outputs. At least two inputs must map to the same output.
\[ \boxed{\text{The function cannot be injective.}} \]Practice 8
\[ \left\lceil\frac{250}{12}\right\rceil = \left\lceil20.833\ldots\right\rceil = \boxed{21}. \]Practice 9
To avoid \(4\) people in one month, each of the \(12\) months may contain at most \(3\) people:
\[ 12\cdot3=36. \]Therefore,
\[ \boxed{37} \]people guarantee that at least \(4\) share a birth month.
Practice 10
The generalized pigeonhole principle uses the ceiling:
\[ \left\lceil\frac{20}{6}\right\rceil = \left\lceil3.333\ldots\right\rceil = 4. \]Therefore,
\[ \boxed{\text{some box contains at least }4\text{ objects}.} \]What to Remember
The basic pigeonhole principle says:
\[ \boxed{n+1\text{ objects in }n\text{ boxes} \Longrightarrow \text{some box contains at least }2.} \]The generalized form says:
\[ \boxed{\text{some box contains at least } \left\lceil\frac{N}{k}\right\rceil \text{ objects}.} \]To guarantee at least \(r\) objects in one of \(k\) boxes:
\[ \boxed{k(r-1)+1}. \]- Identify the pigeons and pigeonholes.
- Use the ceiling when distributing \(N\) objects among \(k\) boxes.
- Use capacity arguments to find guarantee thresholds.
- Choose categories that make a shared pigeonhole imply the desired result.
- Remember that the conclusion usually proves existence, not location.
Where We Go Next
The pigeonhole principle proves that certain collisions or repetitions must occur. Another major counting strategy proves that two sets have the same size by pairing their elements, or counts the same collection in two different ways.
The next lesson, Bijections and Double Counting, develops these structural methods for proving counting identities and comparing finite sets.