math.wiki
Logic, proof and discrete math › Proof techniques › The pigeonhole principle
Open on the map
Discrete Mathematics and Proof

The pigeonhole principle

More things than places to put them. What does that force, and how do you decide what the things and the places are?

You need
Remainders and what they meanGrade 4Existence proofDiscrete Mathematics and ProofDirect proofGrades 9 to 12
Where you are 14 in Proof techniques
Logic, proof and discrete math6
Proof techniques14
▴ 8 aboveProof by casesProof by contraposition
The pigeonhole principle
Proof by contradictionCombinatorial proof: counting one set two ways▾ Show all 14 (1 more)

When you reach for it

Some claims say that in every arrangement of a collection, two members must share something: two chosen numbers add to a fixed total, two points sit close together, two guests know the same number of people. Listing arrangements cannot prove such a claim. The pigeonhole principle proves it in one stroke. It is a tool of existence proof: it shows that a pair with the property exists, usually without saying which pair.

The principle itself is close to obvious. The skill is in the setup: deciding what the objects (the “pigeons”) are and what the boxes (the “holes”) are, so that two objects in one box gives exactly the conclusion wanted.

The procedure

This lesson takes two days. Day 1 is the principle and the setup; Day 2 is the generalized principle and longer arguments. Examples 1 to 3 go with Day 1, Examples 4 to 7 with Day 2.

Day 1: the principle and why it is true

The pigeonhole principle. If more than k objects are placed in k boxes, then some box holds at least two of them.

Proof. Suppose, for contradiction, that every box holds at most one object. Adding over the k boxes, there are at most k objects in all. But there are more than k. This contradiction shows that some box holds at least two objects. \square

The same fact in the language of functions: placing each object of a finite set A in a box from a finite set B is a function f : A \to B. If \lvert A \rvert > \lvert B \rvert, then f is not injective, so there are a \ne a' in A with f(a) = f(a'). This is the finite size rule of One-to-one, onto and bijective functions read backward.

Day 1: choosing the pigeons and the holes

Three things have to hold for the argument to work, and each worked example checks them.

  • Every object lands in a box. The boxes must cover all the possibilities, so that the placement really is a function. When a point could belong to two boxes, as on a shared edge, assign it to one of them by a fixed rule.
  • More objects than boxes. Count both. Often the boxes are built from the problem, and the count of boxes is the number to beat.
  • Two in one box gives the conclusion. This is the creative part. Boxes are chosen so that “same box” means “these two add to 13”, “these two are within \displaystyle 2\sqrt{2} meters”, “these two leave the same remainder”. With remainders, the step from “same remainder” to “the difference is a multiple” is the one from Remainders and what they mean: if a = nq + r and b = nq' + r, then a - b = n(q - q').

Sharpness. A pigeonhole bound is sharp when one fewer object can be placed with no two in a box. Showing this takes a single example, a witness that the count cannot be lowered.

Day 2: the generalized principle

For a real number x, the ceiling \lceil x \rceil is the smallest integer that is at least x. So \lceil 3.2 \rceil = 4, \lceil 5 \rceil = 5 and \lceil -1.5 \rceil = -1. By definition \lceil x \rceil - 1 < x \le \lceil x \rceil.

The generalized pigeonhole principle. If n objects are placed in k boxes, where k \ge 1, then some box holds at least \left\lceil \dfrac{n}{k} \right\rceil objects.

Proof. Write c = \left\lceil \dfrac{n}{k} \right\rceil. Suppose, for contradiction, that every box holds at most c - 1 objects. Since c - 1 < \dfrac{n}{k}, the total is

\text{at most } k(c - 1) < k \cdot \frac{n}{k} = n

so there are fewer than n objects, which is false. Hence some box holds at least c. \square

With n = k + 1, the ceiling is \displaystyle \lceil 1 + \frac{1}{k} \rceil = 2, which is the Day 1 principle. The bound is always sharp. Divide with remainder, n = qk + r with 0 \le r < k, and put q + 1 objects in r of the boxes and q in the others. No box exceeds \lceil n/k \rceil, which is q when r = 0 and q + 1 when r > 0. Turned around: to force at least m + 1 objects into some box of k, you need km + 1 objects, and km objects can be spread m to a box.

Worked examples

Example 1

Two chosen numbers that add to 2n + 1

Let n be a positive integer. Prove that among any n + 1 different numbers chosen from 1, 2, \ldots, 2n, two add to 2n + 1. Show that n numbers are not enough.

Solution

The pigeons are the chosen numbers. For the holes, pair each number with its partner toward 2n + 1:

\{1, 2n\},\ \{2, 2n - 1\},\ \ldots,\ \{n, n + 1\}

Each pair adds to 2n + 1. Every number j from 1 to 2n is in exactly one pair, the one with 2n + 1 - j, so every chosen number lands in a box. There are n boxes.

Proof. Place each of the n + 1 chosen numbers in its pair. There are more numbers than pairs, so by the pigeonhole principle some pair receives two chosen numbers. A pair has only two members, and the chosen numbers are different, so both members of that pair were chosen. They add to 2n + 1. \square

For sharpness, choose 1, 2, \ldots, n: any two add to at most (n - 1) + n = 2n - 1.

With n = 6 the boxes are \{1, 12\}, \{2, 11\}, \{3, 10\}, \{4, 9\}, \{5, 8\}, \{6, 7\}. The seven numbers 2, 3, 5, 8, 9, 11, 12 fill the boxes of 2 and 5 twice, and indeed 2 + 11 = 13 and 5 + 8 = 13.

Example 2

Sensors in a square field

Kiona places 10 soil sensors anywhere in a square field 6 meters on a side, edges included. Prove that two of the sensors are at most \displaystyle 2\sqrt{2} meters apart, and show that 9 sensors can all be farther apart than that.

Solution

Two points in one small square are close, so the holes should be small squares. Cut the field into nine squares 2 meters on a side by two lines each way, as on the left of Figure 1. A sensor on a cut line or a shared corner lies in more than one small square; put it in the lowest, then leftmost, of them, so each sensor is in exactly one box.

10 sensors 9 sensors 6 m 6 m
Figure 1Left, ten sensors in nine squares, so one square (shaded) holds two. Right, nine sensors with every pair at least 3 meters apart.

Proof. Ten sensors go into nine squares, so some square holds two of them, at (x_1, y_1) and (x_2, y_2). Both lie in a square of side 2, so \lvert x_1 - x_2 \rvert \le 2 and \lvert y_1 - y_2 \rvert \le 2. Their distance is

\sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2} \le \sqrt{4 + 4} = 2\sqrt{2}

meters. \square

For sharpness, put nine sensors at the points whose coordinates are each 0, 3 or 6, as on the right of Figure 1. Two different points of this grid differ by at least 3 in some coordinate, so they are at least 3 meters apart, and \displaystyle 3 > 2\sqrt{2} because 9 > 8.

Example 3

A multiple written with ones and zeros

Prove that every positive integer n has a positive multiple whose decimal digits are all 1s and 0s.

Solution

The pigeons are numbers made of ones: let R_j be the number written with j ones, so R_1 = 1, R_2 = 11, R_3 = 111. The holes are the n possible remainders on division by n, namely 0, 1, \ldots, n - 1.

Proof. Take the n + 1 numbers R_1, R_2, \ldots, R_{n+1}. They have only n possible remainders, so two of them, R_i and R_j with i < j, have the same remainder. Then n divides R_j - R_i. Subtracting the last i ones from R_j leaves j - i ones followed by i zeros:

R_j - R_i = \underbrace{1 \cdots 1}_{j - i}\,\underbrace{0 \cdots 0}_{i}

This number is positive, its digits are 1s and 0s, and it is a multiple of n. \square

For n = 6: the remainders of 1, 11, 111, 1111 are 1, 5, 3, 1. The first and fourth agree, and 1111 - 1 = 1110 = 6 \cdot 185.

Example 4

A day of the week that comes up 53 times

Prove that in any year of 365 days, some day of the week occurs at least 53 times. How many different dates must be listed to be sure that at least 10 of them fall on the same day of the week?

Solution

The objects are the 365 days and the boxes are the 7 days of the week. Since 365 = 52 \cdot 7 + 1,

\left\lceil \frac{365}{7} \right\rceil = \left\lceil 52\tfrac{1}{7} \right\rceil = 53

so by the generalized principle some day of the week occurs at least 53 times.

For the second question, 10 = 9 + 1, so with 7 boxes the count needed is 7 \cdot 9 + 1 = 64. Any 64 dates put at least \lceil 64/7 \rceil = 10 on one day of the week. And 63 dates are not enough: 63 days in a row are nine full weeks, nine of each day.

Example 5

A run of terms whose sum is divisible by n

Prove that among any n integers a_1, a_2, \ldots, a_n, some run of one or more consecutive terms a_{i+1} + a_{i+2} + \cdots + a_j has a sum divisible by n. Find such runs for 4, 9, 2, 7, 11, 5.

Solution

The pigeons are the partial sums

S_0 = 0,\quad S_j = a_1 + a_2 + \cdots + a_j \ \ (1 \le j \le n)

and a run is a difference of two of them: S_j - S_i = a_{i+1} + \cdots + a_j when i < j.

Proof. The n + 1 partial sums S_0, S_1, \ldots, S_n have only n possible remainders on division by n. So two of them, S_i and S_j with i < j, have the same remainder, and n divides S_j - S_i = a_{i+1} + \cdots + a_j. Since i < j the run has at least one term. \square

Including S_0 = 0 is what makes n + 1 pigeons out of n terms. For 4, 9, 2, 7, 11, 5, with n = 6:

jS_jremainder
000
144
2131
3153
4224
5333
6382

The remainder 4 appears at j = 1 and j = 4, giving the run 9 + 2 + 7 = 18. The remainder 3 appears at j = 3 and j = 5, giving 7 + 11 = 18. Both are divisible by 6.

Example 6

Two guests who know the same number of guests

Halona hosts a party with n \ge 2 guests. Knowing is mutual: if one guest knows another, the second knows the first. Prove that two guests know the same number of other guests at the party.

Solution

The pigeons are the guests, and each goes in the box of the number of other guests they know. That number is one of 0, 1, \ldots, n - 1: that is n boxes for n guests, one too many. The work is to show that two of these boxes cannot both be used.

Proof. If some guest knows nobody, then no guest knows all n - 1 others, since that guest would know the one who knows nobody, and knowing is mutual. So the boxes 0 and n - 1 are never both used, and the guests fall into at most n - 1 boxes. There are n guests, so by the pigeonhole principle two of them are in one box: they know the same number of other guests. \square

Example 7

Long increasing or decreasing runs (Erdos and Szekeres)

A subsequence of a sequence keeps some of its terms in their original order, not necessarily next to each other. It is increasing when each term is larger than the one before, decreasing when each is smaller. Prove that if m and n are positive integers, every sequence of mn + 1 different real numbers has an increasing subsequence of m + 1 terms or a decreasing subsequence of n + 1 terms. Show that mn terms are not enough.

Solution

The holes here are pairs of numbers. Write the sequence x_1, x_2, \ldots, x_{mn+1}, and give each term x_j two labels: u_j, the length of the longest increasing subsequence that ends at x_j, and d_j, the length of the longest decreasing subsequence that ends at x_j. Both are at least 1, since x_j alone counts.

Proof. Suppose, for contradiction, that there is no increasing subsequence of m + 1 terms and no decreasing subsequence of n + 1 terms. Then every u_j is one of 1, \ldots, m and every d_j one of 1, \ldots, n, so the label pair (u_j, d_j) takes at most mn values. There are mn + 1 terms, so two terms x_i and x_j with i < j have the same pair.

The terms are different, so x_i < x_j or x_i > x_j. If x_i < x_j, then x_j can be added to the end of a longest increasing subsequence ending at x_i, so u_j \ge u_i + 1. If x_i > x_j, the same step on a decreasing subsequence gives d_j \ge d_i + 1. Either way the pairs differ, a contradiction. \square

With m = n = 3, any 10 different numbers have a monotone subsequence of 4 terms. For the sequence 4, 9, 1, 7, 10, 3, 6, 2, 8, 5 the labels are:

x_ju_jd_j
411
921
112
722
1031
323
633
224
842
534

The label u = 4 at 8 comes from 1, 3, 6, 8, and d = 4 at 2 comes from 9, 7, 3, 2. For sharpness, the nine terms 7, 8, 9, 4, 5, 6, 1, 2, 3 have no monotone subsequence of 4: an increasing one stays inside one block of three, and a decreasing one takes at most one term from each block. Blocks like these show that mn terms are not enough for any m and n.

Boundaries

Finite sets only. The principle counts. Between infinite sets, “more” stops meaning what it does for finite ones: n \mapsto 2n sends the natural numbers one to one into the even numbers, a proper part of them. Comparing infinite sizes is the subject of Matching two sets one to one.

Every object must land in exactly one box. If the boxes miss a case, the count of boxes is wrong; if a point lies in two boxes, it must be assigned to one, as in Example 2.

“At least”, not “exactly”. The principle gives at least two in some box, or at least \lceil n/k \rceil. It does not say which box, and the box may hold more.

The conclusion is only as strong as the boxes. Two objects in a box share whatever the box was built to mean, and nothing else. Same remainder on division by 12 means the difference is a multiple of 12, not that it equals 12.

Equal counts force nothing. Exactly k objects can sit one to a box, which is why Example 6 first removes a box.

Where this goes next

The principle is the first of the counting tools in this unit. Counting how many ways objects can fill boxes is Combinations with repetition: stars and bars, and counting objects that fall into overlapping boxes is the Inclusion-exclusion for three or more sets, and derangements. The function view, no injection from a larger finite set to a smaller one, is the finite case of the size comparisons in Matching two sets one to one and Countable sets. Ramsey theory grows from questions like the six-person problem in Existence proof: how large must a structure be before some orderly piece of it is forced?

Exercises

Day 1: choosing the pigeons and the holes

  1. Prove that among any 9 different numbers chosen from 1, 2, \ldots, 15, two add to 16. Show that 8 numbers are not enough.
  2. Prove that among any 11 different numbers chosen from 1, 2, \ldots, 20, two differ by exactly 10. Show that 10 numbers are not enough.
  3. Five points lie in an equilateral triangle of side 2, edges included. Prove that two of them are at most 1 apart. (A segment inside a triangle is never longer than the triangle’s longest side.)
  4. Nine runners stand on a circular track 400 meters around. Prove that two of them are less than 50 meters apart, measured along the track. Show that eight runners can all be at least 50 meters apart.
  5. Prove that among any 7 integers there are two whose squares differ by a multiple of 10.
  6. Prove that some positive multiple of 13 has decimal digits that are all 7s and 0s. Then check that 777777 is a multiple of 13.
  7. A club has 677 members, and each member’s initials are two capital letters of the 26-letter alphabet. Prove that two members have the same initials.

Day 2: the generalized principle

  1. Find \lceil 17/5 \rceil, \lceil 40/8 \rceil, \lceil 2.01 \rceil and \lceil -7/2 \rceil.
  2. Prove that among any 100 integers, at least 12 have the same remainder on division by 9. Show that 13 cannot be promised.
  3. A school has 1{,}200 students, each with a phone number. Prove that at least 12 of them have phone numbers with the same last two digits.
  4. How many integers must be chosen to be sure that at least 6 of them have the same remainder on division by 4? Show that one fewer is not enough.
  5. For the five integers 3, 8, 6, 1, 9, use partial sums to find a run of consecutive terms whose sum is divisible by 5.
  6. Show that the four integers 1, 1, 1, 1 have no run of consecutive terms whose sum is divisible by 5, so the count in Example 5 cannot be lowered.
  7. Prove that every sequence of 17 different real numbers has an increasing or a decreasing subsequence of 5 terms. Give a sequence of 16 different numbers with neither.
  8. Find a monotone subsequence of 4 terms in 6, 2, 9, 4, 7, 1, 10, 3, 8, 5, and say whether it has a decreasing subsequence of 4 terms.

Day 2: reasoning

  1. Prove that among any 5 integers there are 3 whose sum is divisible by 3.
  2. Prove that among any n + 1 different numbers chosen from 1, 2, \ldots, 2n, one divides another. (Write each number as a power of 2 times an odd number.) Show that n numbers are not enough.
  3. Each square of a grid with 3 rows and 9 columns is colored black or white. Prove that there are two rows and two columns whose four shared squares all have the same color.
  4. In a tournament of 8 teams, every two teams play once and there are no ties. Must two teams have the same number of wins? Explain where the argument of Example 6 breaks.
  5. Prove that if n objects are placed in k boxes and n < k, some box is empty.
  6. A drawer holds 10 red socks and 10 blue socks. Taking socks without looking, how many make sure of two of one color? Of two blue socks? Which answer is a pigeonhole count?
  7. Find the flaw: “Any 13 integers include two with the same remainder on division by 12, so any 13 integers include two that differ by exactly 12.” Give 13 integers that show the conclusion is false.
  8. Show that the proof in Example 7 needs the terms to be different, by giving a sequence of 10 real numbers with no increasing and no decreasing subsequence of even 2 terms. Which sentence of the proof fails?
Answers
  1. Boxes \{1, 15\}, \{2, 14\}, \ldots, \{7, 9\} and \{8\}: eight boxes covering 1 to 15. Nine numbers put two in one box. The box \{8\} cannot hold two different numbers, so it is a pair, and they add to 16. The eight numbers 1, \ldots, 8 have largest sum 7 + 8 = 15.
  2. Boxes \{j, j + 10\} for j = 1, \ldots, 10 cover 1 to 20. Eleven numbers put two in one box, and they differ by 10. The numbers 1, \ldots, 10 differ by at most 9.
  3. Join the midpoints of the three sides. This cuts the triangle into four equilateral triangles of side 1. Five points in four triangles (a point on a shared edge assigned to one of them) put two in one small triangle, and a segment inside it is at most 1 long.
  4. Cut the track into eight arcs of 50 meters, each including its starting point but not its end point. Nine runners put two on one arc, less than 50 meters apart. Eight runners spaced evenly are 50 meters from each neighbor, so any two are at least 50 meters apart.
  5. The last digit of a square depends only on the last digit of the number: 0, 1, 4, 9, 6, 5, 6, 9, 4, 1 for last digits 0 to 9. So a square ends in one of 0, 1, 4, 5, 6, 9: six boxes. Seven integers give two squares with the same last digit, and their difference ends in 0, a multiple of 10.
  6. Let T_j be the number written with j sevens. Of T_1, \ldots, T_{14}, two, T_i and T_j with i < j, share a remainder on division by 13, so 13 divides T_j - T_i, which is j - i sevens followed by i zeros. Check: 777777 = 13 \cdot 59829.
  7. There are 26 \cdot 26 = 676 possible pairs of initials, and 677 > 676, so two members share a pair.
  8. \lceil 17/5 \rceil = \lceil 3.4 \rceil = 4, \lceil 40/8 \rceil = 5, \lceil 2.01 \rceil = 3 and \lceil -7/2 \rceil = \lceil -3.5 \rceil = -3.
  9. Nine remainders are the boxes, and \lceil 100/9 \rceil = \lceil 11.1\ldots \rceil = 12. The integers 0, 1, \ldots, 99 have remainder 0 twelve times (0, 9, \ldots, 99) and each other remainder eleven times, so no remainder appears 13 times.
  10. There are 100 possible last two digits, 00 to 99, and \lceil 1200/100 \rceil = 12.
  11. 21, since 6 = 5 + 1 and 4 \cdot 5 + 1 = 21. The twenty integers 1, \ldots, 20 have each remainder exactly five times.
  12. Partial sums 0, 3, 11, 17, 18, 27 have remainders 0, 3, 1, 2, 3, 2. Remainder 3 at S_1 and S_4 gives 8 + 6 + 1 = 15; remainder 2 at S_3 and S_5 gives 1 + 9 = 10.
  13. Every run of consecutive terms sums to 1, 2, 3 or 4, and none of these is divisible by 5.
  14. 17 = 4 \cdot 4 + 1, so Example 7 with m = n = 4 applies. The sequence 13, 14, 15, 16, 9, 10, 11, 12, 5, 6, 7, 8, 1, 2, 3, 4 has longest increasing and decreasing subsequences of 4 terms.
  15. 2, 4, 7, 10 is increasing (so is 2, 4, 7, 8). There is no decreasing subsequence of 4: the longest decreasing subsequence ending at each term has length 1, 2, 1, 2, 2, 3, 1, 3, 2, 3, so the longest has 3 terms, for example 6, 4, 1.
  16. Sort by remainder on division by 3. If all of 0, 1, 2 appear, one of each sums to a multiple of 3 plus 0 + 1 + 2 = 3. Otherwise the five use at most two boxes, so one holds at least \lceil 5/2 \rceil = 3, and three with remainder r sum to a multiple of 3 plus 3r.
  17. Each chosen number is 2^e q with q odd and 1 \le q \le 2n - 1, so there are n possible odd parts q. With n + 1 numbers, two share an odd part: a = 2^e q and b = 2^f q with e < f, since they differ. Then b = 2^{f - e} a, so a \mid b. The n numbers n + 1, \ldots, 2n fail: the smallest multiple of one of them other than itself is at least 2(n + 1) > 2n.
  18. A column has 3 squares in 2 colors, so 2^3 = 8 possible color patterns. Nine columns put two columns in the same pattern. In that pattern, 3 squares in 2 colors give two squares of the same color, in two rows. Those two rows and the two columns give four squares of one color.
  19. No. Rank the teams 1 to 8 and let the higher-ranked team win every game. The win counts are 7, 6, 5, 4, 3, 2, 1, 0, all different. In Example 6, a guest who knows nobody rules out one who knows everyone; here 0 wins and 7 wins can occur together.
  20. Suppose every box holds at least one object. Then there are at least k objects, but n < k. This contradiction shows some box is empty.
  21. 3 and 12. Three socks in two color boxes put two in one box; two socks may differ. For two blue, eleven socks may be ten red and one blue, so 12 are needed. Only 3 is a pigeonhole count; 12 is a worst case that rests on there being 10 red socks.
  22. A shared remainder gives a difference that is a multiple of 12, which may be 24 or more. The integers 0, 1, \ldots, 11, 24 include no two that differ by exactly 12.
  23. Ten equal terms, 5, 5, \ldots, 5: no two terms satisfy < or >. The sentence “the terms are different, so x_i < x_j or x_i > x_j” fails, since here x_i = x_j.
kg1128 · updated 2026-10-22 · CC-BY-SA-4.0