The Central Idea
Suppose
\[ n+1 \]objects are placed into
\[ n \]boxes.
If every box contained at most one object, then the boxes could hold at most \(n\) objects.
But there are \(n+1\) objects.
Therefore,
\[ \boxed{\text{at least one box contains at least two objects}.} \]The Pigeonhole Principle
The basic pigeonhole principle states:
If more than \(n\) objects are distributed among \(n\) categories, then at least one category contains at least two objects.
Symbolically, if
\[ N>n, \]then distributing \(N\) objects among \(n\) boxes forces a collision.
Pigeons and Holes Are Abstract Roles
The words pigeons and holes are only labels.
The pigeons might be:
- people;
- integers;
- points;
- files;
- graph vertices;
- subsets;
- states of an algorithm.
The holes might be:
- birth months;
- remainder classes;
- intervals;
- possible values;
- colors;
- categories defined by a property.
The Key Proof Question
A pigeonhole proof usually depends on identifying two things:
- What are the objects?
- What are the categories into which they must fall?
Once the categories are chosen correctly, the counting argument is often immediate.
A First Example: Birth Months
Suppose there are \(13\) people.
There are only
\[ 12 \]possible birth months.
Treat the people as pigeons and the months as holes.
Since
\[ 13>12, \]at least two people must have been born in the same month.
Why the Principle Is a Proof
The conclusion does not depend on knowing which people share a month.
We do not need to construct the pair.
The counting alone guarantees that some pair exists.
Pigeonhole reasoning is therefore often an existence proof without explicit construction.
Proof by Contradiction Form
The pigeonhole principle can be proved by contradiction.
Suppose \(n+1\) objects are placed into \(n\) boxes and no box contains two objects.
Then every box contains at most one object.
Therefore the total number of objects is at most
\[ n. \]But there are \(n+1\) objects.
This contradiction proves the principle.
The Generalized Pigeonhole Principle
The basic principle guarantees a repeated category.
The generalized form gives a lower bound on how crowded some category must be.
If \(N\) objects are distributed among \(k\) boxes, then some box contains at least
\[ \boxed{\left\lceil\frac{N}{k}\right\rceil} \]objects.
Why the Ceiling Appears
The average occupancy is
\[ \frac{N}{k}. \]If every box contained fewer than
\[ \left\lceil\frac{N}{k}\right\rceil \]objects, then every box would contain at most
\[ \left\lceil\frac{N}{k}\right\rceil-1. \]The total capacity would then be too small to hold all \(N\) objects.
Example: 100 People and 12 Months
Among \(100\) people, some birth month contains at least
\[ \left\lceil\frac{100}{12}\right\rceil = \left\lceil8.333\ldots\right\rceil = 9 \]people.
Therefore,
\[ \boxed{\text{at least 9 people share a birth month}.} \]A Capacity Formulation
Another useful form says:
If every box can hold at most \(r\) objects without violating the desired conclusion, then \(k\) boxes can hold at most
\[ kr \]such objects.
Therefore, if
\[ N>kr, \]at least one box must contain at least \(r+1\) objects.
Example: At Least Four Share a Category
Suppose \(31\) objects are divided among \(10\) categories.
If every category contained at most \(3\) objects, then at most
\[ 10\cdot3=30 \]objects could be placed.
Since there are \(31\),
\[ \boxed{\text{some category contains at least }4\text{ objects}.} \]Remainder Classes as Pigeonholes
Modular arithmetic provides natural categories.
Every integer belongs to exactly one residue class modulo \(m\):
\[ 0,1,\ldots,m-1. \]Therefore any collection of more than \(m\) integers contains two with the same remainder modulo \(m\).
Example: Same Remainder Modulo 5
Choose any \(6\) integers.
There are only \(5\) possible remainders modulo \(5\):
\[ 0,1,2,3,4. \]Therefore at least two chosen integers have the same remainder modulo \(5\).
Same Remainder Gives Divisibility of a Difference
If integers \(a\) and \(b\) have the same remainder modulo \(m\), then
\[ a\equiv b\pmod m. \]Therefore,
\[ m\mid(a-b). \]This turns a pigeonhole collision into a divisibility conclusion.
Example: Difference Divisible by 7
Choose any \(8\) integers.
There are only \(7\) residue classes modulo \(7\).
Hence two chosen integers, say \(a\) and \(b\), satisfy
\[ a\equiv b\pmod7. \]Therefore,
\[ \boxed{7\mid(a-b).} \]Intervals as Pigeonholes
A geometric or numerical range can be divided into subintervals.
If more points are placed than there are subintervals, two points must fall into the same subinterval.
This can force two numbers or points to be close together.
Example: Two Numbers within Distance \(1/5\)
Choose \(6\) numbers from the interval
\[ [0,1]. \]Divide the interval into five pieces:
\[ \left[0,\frac15\right], \left[\frac15,\frac25\right], \ldots, \left[\frac45,1\right]. \]With a suitable convention for shared endpoints, every chosen number belongs to one of \(5\) subintervals of length \(1/5\).
Since \(6>5\), two numbers lie in the same subinterval.
Their distance is therefore at most
\[ \boxed{\frac15}. \]Endpoint Conventions Matter
When intervals share endpoints, define the boxes so each object belongs to exactly one box.
For example, use
\[ \left[0,\frac15\right), \left[\frac15,\frac25\right), \ldots \]with the final interval closed on the right.
Precise box definitions prevent ambiguity.
Pairs as Pigeonholes
Sometimes the best categories are specially constructed pairs or groups.
A classic strategy pairs objects so that selecting too many items forces both members of some pair to be chosen.
Example: Two Consecutive Integers
Choose \(6\) integers from
\[ \{1,2,\ldots,10\}. \]Pair the numbers as
\[ \{1,2\},\{3,4\},\{5,6\},\{7,8\},\{9,10\}. \]These are \(5\) boxes.
Choosing \(6\) integers forces both members of at least one pair to be chosen.
Therefore the chosen set contains two consecutive integers.
Choosing the Boxes Is the Creative Step
In difficult pigeonhole problems, the arithmetic may be trivial once the correct boxes are identified.
The main challenge is designing categories so that:
- every object belongs somewhere;
- the number of boxes is limited;
- a collision inside one box gives the desired conclusion.
Example: Same Last Digit
Choose any \(11\) nonnegative integers.
Their last decimal digits lie in
\[ \{0,1,2,\ldots,9\}. \]These \(10\) possible last digits are the boxes.
Therefore two chosen integers have the same last digit.
Example: Same Parity
Choose any \(3\) integers.
There are only two parity classes:
\[ \text{even},\qquad\text{odd}. \]Therefore at least two chosen integers have the same parity.
Same Parity Gives an Even Difference
If two integers have the same parity, then their difference is even.
Thus among any \(3\) integers, there exist two whose difference is divisible by \(2\).
This is the modulo \(2\) version of the remainder-class argument.
Pigeonhole Reasoning with Functions
A function
\[ f:A\to B \]assigns every element of \(A\) to one element of \(B\).
If
\[ |A|>|B|, \]then \(f\) cannot be injective.
At least two distinct inputs must share the same output.
Finite Functions and Collisions
If a finite function maps \(N\) inputs into only \(k
This is exactly the pigeonhole principle expressed in function language.
Example: Hash Collisions
Suppose a hash function maps \(1000\) possible inputs into \(100\) hash values.
Since there are more inputs than outputs, the function cannot be injective.
Therefore at least two distinct inputs have the same hash value.
A collision is unavoidable.
Repeated States in Finite Systems
Suppose a deterministic process has only \(N\) possible states.
If the process visits
\[ N+1 \]states, then some state must repeat.
In a deterministic system, once a state repeats, the subsequent evolution repeats as well.
This is a common route to proving eventual periodicity.
Example: Eventual Repetition
Consider a deterministic machine with \(50\) possible states.
Record the first \(51\) states visited.
By the pigeonhole principle, two of those states are identical.
Therefore the process has entered a cycle or repeated part of its trajectory.
Pigeonhole Reasoning in Graphs
A simple graph on \(n\) vertices gives each vertex a degree from
\[ 0 \]through
\[ n-1. \]At first there appear to be \(n\) possible degree values for \(n\) vertices.
But a simple graph cannot simultaneously contain both a vertex of degree \(0\) and a vertex of degree \(n-1\).
Therefore only \(n-1\) degree values can actually occur in one graph.
Example: Two Vertices Have the Same Degree
In every simple graph with at least two vertices, two vertices have the same degree.
There are \(n\) vertices but at most \(n-1\) degree values available within a single graph.
Therefore two vertices must share a degree.
Subsets and Pigeonhole Reasoning
Sometimes the pigeons are subsets and the holes are possible values of a statistic.
If more subsets are considered than there are possible values of the statistic, two subsets must produce the same value.
This principle appears frequently in combinatorics.
Partial Sums as Pigeons
Pigeonhole reasoning can be applied to partial sums.
Given integers
\[ a_1,a_2,\ldots,a_n, \]define
\[ S_k=a_1+a_2+\cdots+a_k. \]The residues of the partial sums can force a divisible consecutive block.
Example: A Consecutive Sum Divisible by \(n\)
Given any \(n\) integers
\[ a_1,a_2,\ldots,a_n, \]consider the partial sums
\[ S_1,S_2,\ldots,S_n. \]If some
\[ S_j\equiv0\pmod n, \]then
\[ a_1+\cdots+a_j \]is divisible by \(n\).
Otherwise all \(S_j\) lie among the \(n-1\) nonzero residue classes modulo \(n\).
Since there are \(n\) partial sums, two have the same remainder:
\[ S_i\equiv S_j\pmod n \]
for some \(i
Then
is divisible by \(n\).
Therefore some nonempty consecutive block has sum divisible by \(n\).
Why the Partial-Sum Trick Works
The problem asks about sums of consecutive terms.
A difference of partial sums produces exactly such a sum:
\[ S_j-S_i = a_{i+1}+\cdots+a_j. \]The pigeonhole collision occurs among the residues of the partial sums.
The subtraction converts that collision into the desired divisibility.
Pigeonhole Reasoning and Geometry
Geometric regions can be partitioned into smaller cells.
If enough points are placed in the larger region, two points must lie in the same smaller cell.
The diameter of a cell then bounds the distance between those two points.
Example: Points in a Unit Square
Place \(5\) points in a unit square.
Divide the square into four smaller squares of side length
\[ \frac12. \]Since \(5>4\), two points lie in the same small square.
The diagonal of a small square has length
\[ \sqrt{\left(\frac12\right)^2+\left(\frac12\right)^2} = \frac{\sqrt2}{2}. \]Therefore two of the points are at distance at most
\[ \boxed{\frac{\sqrt2}{2}}. \]Generalized Geometric Pattern
To prove that two points must be close:
- partition the region into cells of controlled diameter;
- place more points than cells;
- force two points into one cell;
- use the cell diameter to bound their distance.
Pigeonhole Reasoning and Repeated Values
Suppose a quantity can take only \(k\) possible values.
Observing it \(k+1\) times guarantees that some value repeats.
This applies to:
- remainders;
- colors;
- degrees;
- machine states;
- finite output values;
- combinatorial signatures.
Pigeonhole Reasoning Can Be Hidden
Some problems never mention boxes, categories, or repetition explicitly.
Signals that pigeonhole reasoning may help include phrases such as:
- “show that two must share...”;
- “prove that some value repeats...”;
- “at least \(r\) objects have...”;
- “there exist two whose difference is divisible by...”;
- “some pair lies within distance...”;
- “a collision must occur...”;
- “eventually a state repeats.”
Reverse-Engineering the Boxes
If the conclusion says two objects share a property, that property often suggests the boxes.
For example, if the goal is to prove
\[ a-b\text{ is divisible by }m, \]then try grouping integers by their remainder modulo \(m\).
A collision in one remainder class produces exactly the desired divisibility.
Common Error: Too Many Boxes
The pigeonhole principle only forces a collision when there are more pigeons than holes.
If \(10\) objects are placed into \(10\) boxes, it is possible for every box to contain exactly one object.
No collision is guaranteed.
Common Error: Boxes Do Not Cover Every Object
Every pigeon must belong to at least one defined box.
If some objects fall outside the classification, the counting argument no longer covers the whole problem.
State the categories precisely.
Common Error: The Collision Does Not Prove the Goal
A pigeonhole proof is only useful if sharing a box implies the desired relationship.
Choosing arbitrary categories may force a collision that has no connection to the theorem.
Design the holes backward from the conclusion.
Common Error: Using the Average without the Ceiling
Suppose \(10\) objects are placed into \(3\) boxes.
The average is
\[ \frac{10}{3}. \]Since occupancy is integral, the guaranteed lower bound is
\[ \left\lceil\frac{10}{3}\right\rceil=4, \]not \(10/3\) objects.
Common Error: Claiming More Than the Principle Guarantees
If \(13\) people are distributed among \(12\) birth months, the principle guarantees that some month contains at least two people.
It does not guarantee that exactly one pair shares a month.
Several months may contain repeated birthdays.
Common Error: Ambiguous Interval Boxes
If neighboring intervals both contain a shared endpoint, one point may appear to belong to two boxes.
This can be fixed by using half-open intervals or another explicit assignment rule.
Precise categorization keeps the counting clean.
Common Error: Forgetting Distinctness
When the conclusion requires two distinct objects, make sure the pigeons themselves are distinct objects.
A collision means two different pigeons occupy the same box.
It does not mean one object is being counted twice.
A Reliable Procedure for Pigeonhole Proofs
- Identify the objects to be distributed.
- Identify a finite set of categories.
- Count the objects.
- Count the categories.
- Verify that every object belongs to a category.
- Check that the number of objects exceeds the relevant capacity.
- Apply the basic or generalized pigeonhole principle.
- Translate the resulting collision back into the language of the problem.
- State explicitly why the shared category proves the desired conclusion.
Example: Full Pigeonhole Workflow
Prove that among any \(9\) integers, there are two whose difference is divisible by \(8\).
Step 1: Choose the pigeons.
The \(9\) integers are the pigeons.
Step 2: Choose the holes.
Use the \(8\) residue classes modulo \(8\):
\[ 0,1,2,3,4,5,6,7. \]Step 3: Apply pigeonhole reasoning.
Since
\[ 9>8, \]two integers, say \(a\) and \(b\), have the same remainder modulo \(8\).
Therefore,
\[ a\equiv b\pmod8. \]Step 4: Translate the collision.
\[ 8\mid(a-b). \]Hence,
\[ \boxed{\text{among any 9 integers, two differ by a multiple of 8}.} \]Practice 1: Birth Months
Prove that among \(13\) people, at least two share a birth month.
Practice 2: Generalized Pigeonhole Principle
If \(50\) objects are placed into \(7\) boxes, how many objects must some box contain?
Practice 3: Same Remainder
Prove that among any \(6\) integers, two have the same remainder modulo \(5\).
Practice 4: Divisible Difference
Prove that among any \(11\) integers, two have a difference divisible by \(10\).
Practice 5: Same Parity
Prove that among any \(3\) integers, two have the same parity.
Practice 6: Consecutive Integers
Choose \(6\) integers from
\[ \{1,2,\ldots,10\}. \]Prove that two chosen integers are consecutive.
Practice 7: Function Collision
Suppose
\[ f:A\to B \]where
\[ |A|=21,\qquad |B|=20. \]Prove that \(f\) is not injective.
Practice 8: Close Points
Place \(5\) points in a unit square.
Prove that two lie at distance at most
\[ \frac{\sqrt2}{2}. \]Practice 9: Repeated State
A deterministic system has \(100\) possible states.
What can you conclude after recording \(101\) visited states?
Practice 10: Identify the Error
A student places \(8\) objects into \(8\) boxes and says that two objects must share a box.
Explain the error.
Practice Answers
Practice 1
There are \(13\) people and \(12\) birth months.
Since
\[ 13>12, \]at least two people share a birth month.
Practice 2
\[ \left\lceil\frac{50}{7}\right\rceil = \left\lceil7.142\ldots\right\rceil = \boxed{8}. \]Therefore some box contains at least \(8\) objects.
Practice 3
There are \(5\) possible remainders modulo \(5\).
Six integers placed into these \(5\) classes force two into the same class.
Practice 4
Use the \(10\) residue classes modulo \(10\) as boxes.
Among \(11\) integers, two satisfy
\[ a\equiv b\pmod{10}. \]Therefore,
\[ \boxed{10\mid(a-b)}. \]Practice 5
There are only two parity classes: even and odd.
Three integers force at least two into the same class.
Practice 6
Use the five pairs
\[ \{1,2\},\{3,4\},\{5,6\},\{7,8\},\{9,10\}. \]Choosing \(6\) numbers forces both members of some pair to be chosen.
Those two numbers are consecutive.
Practice 7
The \(21\) elements of \(A\) are mapped into only \(20\) possible outputs.
Therefore two distinct elements \(x,y\in A\) satisfy
\[ f(x)=f(y). \]Hence \(f\) is not injective.
Practice 8
Divide the unit square into four squares of side \(1/2\).
Five points placed into four smaller squares force two into the same one.
The greatest possible distance between two points in one smaller square is its diagonal:
\[ \boxed{\frac{\sqrt2}{2}}. \]Practice 9
Among \(101\) visited states and only \(100\) possible states, some state must repeat.
Because the system is deterministic, repetition indicates that the future evolution from that repeated state will also repeat.
Practice 10
With \(8\) objects and \(8\) boxes, it is possible to place exactly one object in each box.
The pigeonhole principle does not force a collision unless the number of objects exceeds the available one-per-box capacity.
What to Remember
The basic pigeonhole principle says:
\[ \boxed{n+1\text{ objects in }n\text{ boxes force a repeated box}.} \]The generalized form says:
\[ \boxed{ N\text{ objects in }k\text{ boxes} \Longrightarrow \text{some box contains at least } \left\lceil\frac Nk\right\rceil. } \]- the objects and boxes are abstract roles;
- choosing the right boxes is usually the main creative step;
- remainder classes are natural boxes for divisibility problems;
- intervals are useful for closeness and geometric arguments;
- function outputs are boxes when proving collisions or non-injectivity;
- finite state spaces force repeated states in sufficiently long processes;
- the boxes must cover every object;
- a collision must translate into the desired conclusion.
The strategic question is: What limited set of categories can I force these objects into so that two of them sharing a category gives exactly the relationship I need?
Where We Go Next
Pigeonhole reasoning forces repetition from limited capacity. Another discrete proof strategy focuses on an object that is largest, smallest, earliest, latest, shortest, or otherwise extreme, then uses that extremal choice to constrain the entire problem.
The next lesson, Extremal Arguments, develops that method.