The Pigeonhole Principle

July 2026 · 16 min read

Basic Pigeonhole Principle

The Pigeonhole Principle (PHP) is deceptively simple: if you place n + 1 objects into n boxes, at least one box must contain two or more objects.

Formally: if f: A → B is a function and |A| > |B|, then f is not injective — there exist distinct a₁, a₂ ∈ A with f(a₁) = f(a₂).

Classic Examples

• Birthday Paradox Setup: In a group of 367 people, at least two share a birthday (since there are at most 366 possible birthdays).
• Socks in a Drawer: A drawer has 10 red and 10 blue socks. Pulling out 3 socks guarantees at least 2 of the same color.
• Handshake Lemma: In any group of n ≥ 2 people, at least two people have shaken the same number of hands.

The Key to Applying PHP

The art lies in identifying what the "pigeons" are and what the "holes" are. This is often the creative step in a proof or solution.

Generalized Pigeonhole

The generalized version states: if n objects are placed into k boxes, at least one box contains ⌈n/k⌉ objects.

If |A| = n objects placed into k boxes:
  max objects in any box ≥ ⌈n/k⌉

Example: Divisibility

Among any n + 1 integers, at least two have the same remainder when divided by n. (Pigeons = integers, Holes = remainders 0, 1, …, n−1.)

Example: Points in a Square

Place 5 points in a unit square. Divide the square into 4 smaller squares of side 1/2. By PHP, at least two points are in the same small square, so they're at most √2/2 ≈ 0.707 apart.

// Demonstrate generalized PHP: find most frequent remainder
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, k;
    cin >> n >> k;

    vector<int> a(n);
    map<int, int> freq;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        freq[a[i] % k]++;
    }

    int max_freq = 0, max_rem = -1;
    for (auto& [rem, cnt] : freq) {
        if (cnt > max_freq) {
            max_freq = cnt;
            max_rem = rem;
        }
    }
    // By PHP: max_freq >= ceil(n / k)
    cout << "Remainder " << max_rem
         << " appears " << max_freq << " times\n";
    cout << "PHP guarantees at least " << (n + k - 1) / k << "\n";
    return 0;
}

The Erdős–Szekeres Theorem

One of the most elegant applications of the pigeonhole principle is the Erdős–Szekeres theorem on monotone subsequences:

Every sequence of more than r · s distinct real numbers contains an increasing subsequence of length r + 1 or a decreasing subsequence of length s + 1.

Proof via Pigeonhole

Let the sequence be a₁, a₂, …, aₙ with n > r · s. For each element aᵢ, let:

• inc(i) = length of the longest increasing subsequence ending at aᵢ
• dec(i) = length of the longest decreasing subsequence ending at aᵢ

Claim: The pairs (inc(i), dec(i)) are all distinct. If i < j, then either aᵢ < aⱼ (so inc(j) > inc(i)) or aᵢ > aⱼ (so dec(j) > dec(i)).

If all inc(i) ≤ r and all dec(i) ≤ s, there are at most r · s distinct pairs — but we have n > r · s elements. Contradiction!

CP Application: Longest Increasing Subsequence Lower Bound

If a sequence of length n has no increasing subsequence of length k + 1, then it can be partitioned into at most k decreasing subsequences (Dilworth's theorem). This gives a lower bound on LIS or LDS.

// LIS in O(n log n) — illustrating the Erdős–Szekeres bound
#include <bits/stdc++.h>
using namespace std;

int lis(vector<int>& a) {
    vector<int> dp;
    for (int x : a) {
        auto it = lower_bound(dp.begin(), dp.end(), x);
        if (it == dp.end()) dp.push_back(x);
        else *it = x;
    }
    return dp.size();
}

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int& x : a) cin >> x;

    int inc_len = lis(a);
    // By Erdős–Szekeres: if inc_len * dec_len < n,
    // then one of them can be extended.
    cout << "LIS length: " << inc_len << "\n";
    // PHP guarantees: longest monotone subseq >= ceil(sqrt(n))
    cout << "PHP lower bound: " << (int)ceil(sqrt(n)) << "\n";
    return 0;
}

Pigeonhole in Number Theory

Many number theory results rely on the pigeonhole principle. Here are key applications.

Subset Sum Divisibility

Theorem: Given any n integers, there exists a non-empty contiguous subsequence whose sum is divisible by n.

Proof: Compute prefix sums S₀ = 0, S₁, S₂, …, Sₙ. There are n + 1 prefix sums and only n possible remainders mod n. By PHP, two prefix sums share a remainder: Sᵢ ≡ Sⱼ (mod n) with i < j. Then Sⱼ − Sᵢ = aᵢ₊₁ + … + aⱼ ≡ 0 (mod n).

// Find a contiguous subarray with sum divisible by n
#include <bits/stdc++.h>
using namespace std;

pair<int,int> find_divisible_subarray(vector<int>& a) {
    int n = a.size();
    vector<int> mod_seen(n, -1);
    mod_seen[0] = 0; // prefix sum 0 has remainder 0 at index 0

    long long prefix = 0;
    for (int i = 0; i < n; i++) {
        prefix += a[i];
        int r = ((prefix % n) + n) % n;
        if (mod_seen[r] != -1) {
            return {mod_seen[r], i + 1}; // subarray [mod_seen[r], i]
        }
        mod_seen[r] = i + 1;
    }
    return {-1, -1}; // unreachable by PHP
}

Repeated Decimal Digits

When computing 1/n in decimal, the remainders cycle because there are only n possible remainders. By PHP, a remainder must repeat within n steps, creating the periodic decimal expansion.

Bézout-Style Arguments

Consider the sequence 1, a, 2a, 3a, …, (n−1)a modulo n where gcd(a, n) = 1. These must be distinct (if ia ≡ ja, then i ≡ j), so they're a permutation of 0, 1, …, n−1. PHP confirms no collisions, proving the residues hit every value.

Pigeonhole and Dirichlet's Approximation

Dirichlet's theorem: For any real α and positive integer N, there exists a fraction p/q with 1 ≤ q ≤ N such that |α − p/q| < 1/(qN).

Proof: Consider fractional parts {α}, {2α}, …, {Nα} — there are N values in [0, 1). Divide [0, 1) into N intervals of length 1/N. By PHP, two fractional parts {iα} and {jα} lie in the same interval, so |(i−j)α − m| < 1/N for some integer m.

Pigeonhole in Competitive Programming

Here are recurring patterns where PHP provides the crucial insight.

Pattern 1: Finding Duplicates

Given an array of n + 1 integers in the range [1, n], find a duplicate. This is the setup for Floyd's cycle detection (tortoise and hare).

// Find duplicate in [1..n] array of size n+1
// Floyd's cycle detection — O(n) time, O(1) space
int find_duplicate(vector<int>& nums) {
    int slow = nums[0], fast = nums[0];
    do {
        slow = nums[slow];
        fast = nums[nums[fast]];
    } while (slow != fast);

    slow = nums[0];
    while (slow != fast) {
        slow = nums[slow];
        fast = nums[fast];
    }
    return slow;
}

Pattern 2: Prefix Sum Remainders

As shown in the number theory section, prefix sums modulo n guarantee a collision. This pattern appears in problems asking for subarrays with sum divisible by k.

Pattern 3: Bounded Value Range

If a sequence of length n has values from a set of size less than n, there must be a repeat. This is useful for detecting cycles in functional graphs.

// Detect cycle in a functional graph f: {0,...,n-1} -> {0,...,n-1}
// By PHP: iterating f(f(f(...))) must eventually cycle
pair<int,int> detect_cycle(int start, function<int(int)> f) {
    // Phase 1: find meeting point
    int slow = f(start), fast = f(f(start));
    while (slow != fast) {
        slow = f(slow);
        fast = f(f(fast));
    }
    // Phase 2: find cycle start
    slow = start;
    while (slow != fast) {
        slow = f(slow);
        fast = f(fast);
    }
    int cycle_start = slow;
    // Phase 3: find cycle length
    int cycle_len = 1;
    fast = f(slow);
    while (fast != slow) {
        fast = f(fast);
        cycle_len++;
    }
    return {cycle_start, cycle_len};
}

Pattern 4: Forced Collisions in Hashing

If a hash function maps to M buckets and we have M + 1 items, a collision is guaranteed. This is why hash table worst-case analysis matters in CP (especially with anti-hash tests).

Pattern 5: Subset Sum Existence

Given n integers, the number of distinct subset sums is at most 2ⁿ. If the range of possible sums is smaller than 2ⁿ, PHP guarantees two subsets share a sum — their symmetric difference gives a subset summing to 0.

A Full Contest Example

Problem: Given n integers where n is odd, prove that you can select (n+1)/2 of them whose sum is divisible by (n+1)/2.

Solution Sketch: Consider all C(n, (n+1)/2) subsets of size (n+1)/2. Their sums take values modulo (n+1)/2. Since there are more subsets than residues, by PHP two subsets share a remainder. But a more elegant argument uses the Erdős–Ginzburg–Ziv theorem (a deep result whose proof relies on PHP).

Practice Problems

Test your PHP skills with these problems:

1. Find the Duplicate Number (LeetCode 287) — Array of n + 1 integers in [1, n]. Find the duplicate in O(n) time and O(1) space.
2. Subarray Divisibility (CSES 1662) — Find the number of subarrays with sum divisible by n. Uses prefix sum + PHP reasoning.
3. Longest Monotone Subsequence — Given a permutation of length n² + 1, find an increasing or decreasing subsequence of length n + 1. (Erdős–Szekeres)
4. Repeated Colors — You have n balls in k colors. What is the minimum n guaranteeing at least m balls of one color? Answer: k · (m − 1) + 1.
5. Points on a Circle — Place 6 points on a circle. Prove that some two are at most r apart (where r is the radius). Divide the circle into 5 arcs.

PHP Quick Reference