Chapter 17 of 30

Pigeonhole Principle

If 11 letters are put into 10 pigeonholes (mail slots), at least one slot must get two letters. That sounds too obvious to be a theorem, yet this simple idea proves surprising facts: two people in Delhi have exactly the same number of hairs on their head, every sequence of 10 distinct numbers hides a monotone run of 4, and among any 6 people there are 3 mutual friends or 3 mutual strangers.

The Pigeonhole Principle is different from the counting rules in Counting Principles and Permutations & Combinations. Those give an exact number. The pigeonhole principle gives an existence guarantee: something must happen, even though we may not know where. The hard part is never the principle itself; it is choosing what the "pigeons" and the "holes" are.

Pigeonhole Principle: if more than k objects are placed into k boxes, then at least one box contains two or more objects.

Every brute-force claim in this chapter (the Ramsey result for 6 people, the monotone subsequence theorem for small cases, the divisibility facts) was checked by a program that tried every possible case.


The Basic Principle and Its Proof

Proof (by contradiction). Suppose k + 1 or more objects go into k boxes and every box has at most 1 object. Then the total number of objects is at most 1 + 1 + … + 1 = k, which contradicts "more than k". ∎

In the language of Functions: if f : A → B and |A| > |B|, then f is not one-to-one. Two different elements of A must share an image. This form is the one used in computer science.

Quick examples

  • Birthdays. Among 13 people, two were born in the same month (13 pigeons, 12 months). Among 367 people, two share a birthday, since there are at most 366 possible dates. Note that 366 people are not enough to guarantee it.

  • Socks. A drawer has red, blue and black socks. Drawing 4 socks guarantees a matching pair (4 socks, 3 colours).

  • Hashing. A hash function maps a huge set of keys (all strings) to a fixed number of buckets, say 232. Since there are more possible keys than buckets, collisions must exist. No hash function can avoid them; good ones just make them rare and hard to find.

  • Compression. No lossless compression program can shrink every file. There are 2n files of exactly n bits but only 20 + 21 + … + 2n−1 = 2n − 1 files shorter than n bits, so two n-bit files would get the same shorter output and could not both be recovered.


The Generalized Pigeonhole Principle

If 25 letters go into 10 slots, some slot must get at least 3, because if every slot had at most 2 there would be at most 20 letters.

Generalized Pigeonhole Principle: if N objects are placed into k boxes, then at least one box contains at least ⌈N/k⌉ objects.

Proof. Suppose every box contains at most ⌈N/k⌉ − 1 objects. Since ⌈N/k⌉ < N/k + 1, we get ⌈N/k⌉ − 1 < N/k. So the total is at most k(⌈N/k⌉ − 1) < k × N/k = N, a contradiction. ∎

The "minimum number" form

Exams usually ask the reverse question: how many objects are needed to guarantee that some box has at least r objects? The worst case puts r − 1 objects in every box, which uses k(r − 1) objects without success. One more forces a box to reach r:

The minimum number of objects that guarantees some box has at least r of them is N = k(r − 1) + 1.

Worked examples

(a) Grades. A course gives 5 grades (A, B, C, D, F). How many students must there be to be sure that at least 5 get the same grade? k = 5, r = 5: N = 5 × 4 + 1 = 21. With 20 students, four of each grade is possible.

(b) Cards of one suit. How many cards must be drawn from a standard 52-card deck to guarantee three cards of the same suit? k = 4 suits, r = 3: N = 4 × 2 + 1 = 9.

(c) Three hearts. How many cards guarantee three hearts? This is not the formula above, because the box is fixed. The worst case draws all 39 non-hearts first, then needs 3 hearts: 39 + 3 = 42. Always think about the worst case directly.

(d) Hairs. A human head has fewer than 106 hairs (around 1 to 1.5 lakh is typical, so this is a very safe bound). A city of 3 crore = 3 × 107 people, sorted into 106 boxes "number of hairs = 0, 1, …, 999999", has some box with at least ⌈3 × 107 / 106⌉ = 30 people. So at least 30 people have exactly the same number of hairs.


Classic Proofs Using Pigeonhole

In each proof below, look at how the boxes are chosen. That choice is the whole idea.

1. Two numbers that differ by 1, and one that divides another

Claim A. Any n + 1 numbers chosen from {1, 2, …, 2n} include two consecutive numbers.

Proof. Make n boxes: {1, 2}, {3, 4}, …, {2n − 1, 2n}. Each chosen number is in exactly one box. n + 1 numbers in n boxes, so some box holds two chosen numbers, and the two numbers in a box are consecutive. ∎

Claim B. Any n + 1 numbers chosen from {1, 2, …, 2n} include two numbers such that one divides the other.

Proof. Write each chosen number as x = 2e × m with m odd (take out all factors of 2). The odd part m lies in {1, 3, 5, …, 2n − 1}, which has only n values. With n + 1 numbers, two of them have the same odd part: x = 2em and y = 2fm with e < f. Then x divides y. ∎

Both claims are sharp: from {1, …, 10} the five numbers 1, 3, 5, 7, 9 have no consecutive pair, and 6, 7, 8, 9, 10 have no pair where one divides the other.

2. A block with sum divisible by n

Claim. Among any n integers a1, …, an, there is a non-empty block of consecutive terms ai+1 + … + aj whose sum is divisible by n.

Proof. Consider the n prefix sums S1 = a1, S2 = a1 + a2, …, Sn. If some Sj ≡ 0 (mod n), the block a1…aj works. Otherwise the n prefix sums have remainders in {1, 2, …, n − 1}, only n − 1 boxes. So two have the same remainder: Si ≡ Sj with i < j. Then Sj − Si = ai+1 + … + aj ≡ 0 (mod n). ∎

Example with n = 6 and the numbers 4, 7, 2, 9, 5, 8:

j          1    2    3    4    5    6
a_j        4    7    2    9    5    8
S_j        4   11   13   22   27   35
S_j mod 6  4    5    1    4    3    5
                          ^
S_1 and S_4 both leave remainder 4, so a_2 + a_3 + a_4 = 7 + 2 + 9 = 18 is divisible by 6.

The same prefix-sum trick appears in coding interviews ("find a subarray whose sum is a multiple of k") where a hash map of remainders finds the repeated remainder in O(n) time.

3. Two people with the same number of friends

Claim. In any group of n ≥ 2 people, where friendship is mutual, two people have the same number of friends within the group.

Proof. Each person has between 0 and n − 1 friends: n possible values for n people, which is not yet enough. But 0 and n − 1 cannot both occur: if someone is friends with everyone, nobody has 0 friends. So the n people actually use at most n − 1 different values, and two of them share a value. ∎

In graph language (which we develop properly in the later chapter Graph Theory Basics): every simple graph with at least two vertices has two vertices of equal degree.

4. Points in a square

Claim. If 5 points are placed inside a square of side 2, some two are at distance at most √2.

Proof. Divide the square into four 1 × 1 squares. Five points, four small squares, so two points lie in the same small square (a point on a shared border can be assigned to either). The farthest two points of a unit square can be is its diagonal, √2. ∎


Monotone Subsequences (Erdős–Szekeres)

Theorem (Erdős–Szekeres, 1935). Every sequence of n2 + 1 distinct real numbers contains an increasing subsequence of length n + 1 or a decreasing subsequence of length n + 1.

A subsequence keeps the original order but may skip terms. For n = 3: any 10 distinct numbers contain a monotone subsequence of length 4.

Proof. Let the sequence be a1, …, an²+1. Suppose it has no increasing subsequence of length n + 1. Give each term a label Lk = the length of the longest increasing subsequence starting at ak. By our assumption every label is in {1, 2, …, n}, so there are n boxes for n2 + 1 terms. By the generalized principle some label is shared by at least ⌈(n2 + 1)/n⌉ = n + 1 terms.

Now take two terms with the same label, as and at with s < t. If as < at, then putting as in front of the longest increasing subsequence starting at at gives one starting at as of length Lt + 1, so Ls > Lt, contradicting equal labels. Hence as > at (they are distinct). So the n + 1 terms sharing a label, read left to right, form a decreasing subsequence of length n + 1. ∎

Seeing the labels

sequence   7   9   3   8   5   2  10   6   4   1
label L    3   2   3   2   2   2   1   1   1   1

label 1:  10, 6, 4, 1     (decreasing, length 4)
label 2:  9, 8, 5, 2      (decreasing, length 4)
label 3:  7, 3

The largest label is 3, so there is no increasing subsequence of length 4, and as the theorem promises, the labels hand us decreasing subsequences of length 4.

The bound is tight: the 9-term sequence 3, 2, 1, 6, 5, 4, 9, 8, 7 has longest increasing and longest decreasing subsequences of length only 3. So n2 terms are not enough.


A Taste of Ramsey Theory: Friends and Strangers

Among any 6 people, there are 3 who are mutual friends or 3 who are mutual strangers. Six is the smallest number with this property, written R(3, 3) = 6.

Proof that 6 people suffice. Pick one person, A. The other 5 are each either A's friend or a stranger to A. By the generalized principle, at least ⌈5/2⌉ = 3 of them fall in the same group; say B, C, D are all friends of A (the stranger case is symmetric, with the words swapped).

  • If any two of B, C, D are friends, those two together with A are 3 mutual friends.

  • If no two of B, C, D are friends, then B, C, D are 3 mutual strangers.

Either way we are done. ∎

Why 5 people are not enough. Seat 5 people in a circle and let each be friends only with the two neighbours. Friendships form a 5-cycle (a pentagon) and strangers form the other 5-cycle (the pentagram of diagonals). A triangle of friends would need a triangle inside a 5-cycle, which does not exist, and the same holds for strangers.

        0                friends   (pentagon):   0-1, 1-2, 2-3, 3-4, 4-0
      /   \              strangers (diagonals):  0-2, 0-3, 1-3, 1-4, 2-4
     4     1
      \   /              No three people are pairwise friends,
      3 - 2              and no three are pairwise strangers.

Verifying by brute force

With 6 people there are C(6, 2) = 15 pairs, so 215 = 32768 ways to mark each pair friend or stranger. A computer can check them all:

from itertools import combinations, product

# Every 2-colouring of the 15 edges of K6 has a monochromatic triangle?
def has_mono_triangle(n, colour):
    for a, b, c in combinations(range(n), 3):
        if colour[(a, b)] == colour[(a, c)] == colour[(b, c)]:
            return True
    return False

edges6 = list(combinations(range(6), 2))
bad = 0
for bits in product((0, 1), repeat=len(edges6)):
    if not has_mono_triangle(6, dict(zip(edges6, bits))):
        bad += 1
print("K6 colourings checked:", 2 ** len(edges6), " without mono triangle:", bad)

# K5: colour the pentagon edges red (0), the diagonals blue (1)
edges5 = list(combinations(range(5), 2))
pent = {(a, b): 0 if (b - a) % 5 in (1, 4) else 1 for a, b in edges5}
print("K5 pentagon colouring has mono triangle?", has_mono_triangle(5, pent))

Output:

K6 colourings checked: 32768  without mono triangle: 0
K5 pentagon colouring has mono triangle? False

The proof is far more elegant than the program, but the program is a useful sanity check. Notice how fast brute force grows: for 10 people there would be 245 colourings, and exact Ramsey numbers like R(5, 5) are still unknown: the best known bounds are 43 ≤ R(5, 5) ≤ 46 (the upper bound was proved in 2024 with heavy computer help), because the search space is far too large to check directly.


How to Attack a Pigeonhole Problem

Step

What to do

Example

1

Spot the signal: "show that there exist two…", "at least", "guarantee", "must"

"Show two numbers differ by 1"

2

Identify the pigeons (the objects you have many of)

The n + 1 chosen numbers

3

Design boxes so that "two in one box" gives what you want

Pairs {1,2}, {3,4}, …

4

Count: pigeons > boxes (or use ⌈N/k⌉)

n + 1 > n

5

For "minimum number" questions, build the worst case explicitly

k(r − 1) objects with no success, then one more

Common box choices: remainders mod n, odd parts, pairs that sum to a constant, sub-squares of a region, possible degree values, labels such as "longest run starting here".


Common Mistakes

  • Off-by-one in the guarantee. 12 people do not guarantee a shared birth month (one per month is possible); 13 do. The answer to "how many guarantee" is always worst case + 1.

  • Using ⌊N/k⌋ instead of ⌈N/k⌉. 25 objects in 10 boxes guarantee ⌈2.5⌉ = 3 in some box, not 2.

  • Applying the formula when a specific box is required (the three hearts example). The formula k(r − 1) + 1 is for "some box", not "this box".

  • Thinking pigeonhole tells you which box. It only proves existence. Finding the collision may still be hard; that is exactly what makes cryptographic hash functions secure.

  • Boxes that overlap or miss objects. Every pigeon must go into exactly one box, otherwise the counting argument breaks.


Practice and GATE-Style Questions

Q1. What is the minimum number of students in a class to be sure that at least 4 of them were born on the same day of the week?

k = 7 days, r = 4: N = 7 × 3 + 1 = 22. With 21 students, three per weekday is possible.

Q2. A bag has 10 red, 8 blue and 6 green balls. How many must be drawn (without looking) to be sure of getting at least 4 balls of one colour? At least 4 green balls?

Any colour: worst case 3 of each colour, 9 balls; so 10. Four green: worst case all 18 red and blue first, then 4 green: 22.

Q3. Show that among any 5 integers, there are two whose difference is divisible by 4.

Boxes: remainders mod 4, namely 0, 1, 2, 3. Five integers, four boxes, so two integers x and y have the same remainder. Then x − y ≡ 0 (mod 4). ∎

Q4. How many numbers must be chosen from {1, 2, …, 20} to guarantee that two of them sum to 21?

Boxes: the 10 pairs {1, 20}, {2, 19}, …, {10, 11}, each summing to 21. Choosing 10 numbers, one from each pair, avoids the sum. The 11th number completes a pair. Answer: 11.

Q5. A sequence of 17 distinct integers is given. What is the guaranteed length of a monotone (increasing or decreasing) subsequence?

17 = 42 + 1, so by Erdős–Szekeres with n = 4 there is a monotone subsequence of length 5. Length 6 is not guaranteed, since even 25 = 52 terms can avoid it.

Q6. Interview: an array of n + 1 integers contains values only from 1 to n. Why must a duplicate exist, and how can you find one in O(1) extra space?

n + 1 values in n possible boxes, so pigeonhole guarantees a duplicate. Treat the array as a function i → a[i]; since a duplicate value means two indices point to the same place, following i → a[i] from index 0 enters a cycle whose entry point is the duplicate. Floyd's tortoise-and-hare cycle detection finds it in O(n) time and O(1) space without modifying the array.


Summary

  • Basic principle: more than k objects in k boxes force a box with at least 2. Equivalently, a function from a larger finite set to a smaller one cannot be one-to-one.

  • Generalized: N objects in k boxes force a box with at least ⌈N/k⌉.

  • Minimum to guarantee r in some box: k(r − 1) + 1. For a specific box, reason about the worst case directly.

  • The art is in choosing boxes: remainders, odd parts, complementary pairs, sub-regions, degree values, or labels.

  • Famous results: Erdős–Szekeres (n2 + 1 distinct numbers give a monotone subsequence of length n + 1) and R(3, 3) = 6.

Pigeonhole proofs never say where the collision is, only that it cannot be avoided. Choose your boxes well and the proof writes itself.