maths.free › Discrete Math & Logic › The pigeonhole principle
The pigeonhole principle
If more objects than boxes, two share a box; the generalised form with ceilings; and how to choose the boxes.
The pigeonhole principle says that if \( n + 1 \) objects are placed in \( n \) boxes, some box holds at least two of them. It sounds too obvious to be useful, and its power lies entirely in choosing what the objects and the boxes are. Among any 13 people, two were born in the same month. Among any five integers, two leave the same remainder on division by 4, so their difference is divisible by 4.
The generalised form: if \( N \) objects go into \( k \) boxes, some box holds at least \( \lceil N/k \rceil \) objects. Otherwise every box holds at most \( \lceil N/k \rceil - 1 < N/k \) objects, and the total is less than \( N \). The example computes \( \lceil 25/6 \rceil = 5 \): among 25 dice rolls some face appears at least 5 times. Read in reverse, it answers "how many objects guarantee" questions: to be sure that some box has \( r \) objects you need \( k(r-1) + 1 \) of them.
The art is in the boxes. Any \( n + 1 \) numbers chosen from \( 1, 2, \dots, 2n \) include two that are consecutive: use the \( n \) boxes \( \{1, 2\}, \{3, 4\}, \dots, \{2n-1, 2n\} \). Any \( n + 1 \) of them include one dividing another: write each number as \( 2^j m \) with \( m \) odd, and box it by \( m \); there are only \( n \) odd numbers up to \( 2n \), so two chosen numbers share \( m \), and the smaller divides the larger. In any sequence of \( n \) integers some consecutive block has a sum divisible by \( n \): box the \( n \) prefix sums by remainder mod \( n \); either one is 0, or two share a remainder and the block between them works.
Picture it: a row of pigeonholes and one more pigeon than holes. However you seat them, one hole is shared. The generalised form is the same picture with the pigeons spread as evenly as possible: the fullest hole still holds at least the average, rounded up.
Think it: the principle proves existence without saying which box is crowded, which is why it appears in proofs rather than algorithms. It is also the finite form of a basic fact about functions: there is no injection from a larger finite set into a smaller one. Ramsey theory grows from repeated, clever applications of it: among any six people there are three mutual acquaintances or three mutual strangers.
Worked example · ceiling(25/6)
Now you Pick a problem, or type or draw your own. Every step, a picture, the answer hidden until you ask.
Symbols used here
Tap any symbol for the full definition, a picture, and what every letter in it means.
How to: The pigeonhole principle
- Identify the objects: what is there more of?
- Choose boxes so that two objects in one box give what you want (same remainder, a consecutive pair, a divisor).
- Count objects N and boxes k and check N > k, or use ceiling(N/k) for the generalised form.
- Conclude that some box has two (or ceiling(N/k)) objects and translate back.
Questions people ask
How many socks must I take from a drawer of red and blue socks to be sure of a pair?
Three. The boxes are the two colours, and three socks in two boxes force two of one colour. To be sure of two red socks you need the number of blue socks plus two.
Does the principle tell me which box has two objects?
No. It is a pure existence statement. Finding the crowded box may need a search, and in some applications (hash collisions, for instance) finding one is exactly the hard part.
What makes mathematics "discrete"?
It deals with separate, countable objects (integers, graphs, statements) rather than continuous quantities. No limits, no infinitesimals; instead induction, counting and logic.
How does a proof by induction work?
Show the statement for the first case, then show that whenever it holds for n it holds for n + 1. Like dominoes: the first falls, and each knocks over the next.
What order should I take these lessons in?
Logic and proof first, because every later lesson proves things. Then induction, sets, relations and functions, counting, recurrences, graphs, Boolean algebra and automata, and finally algorithms and complexity, which use nearly everything before them.
Is discrete mathematics the same as the maths of computer science?
Largely. Data structures are graphs and trees, correctness arguments are induction, running times are recurrences and sums, circuits are Boolean algebra, and what a computer can do efficiently is the subject of the last lessons. It is also ordinary mathematics in its own right.
Do I need calculus for this course?
No. School algebra is enough. A little familiarity with limits helps when comparing growth rates, and the lesson on asymptotic analysis explains the one limit fact it uses.
More in Discrete Math & Logic
Truth tablesSums and inductionProof by inductionAlgorithms and growth of functionsPredicate logic and quantifiersDirect proof, contrapositive and contradictionStrong induction and the well-ordering principleRelations: equivalence relations and partial ordersFunctions and cardinalityCounting: rules, choices and bijectionsSolving linear recurrence relationsGraphs: degrees, paths and connectivityTrees and spanning treesEuler and Hamilton paths