I. In-Class Exercises

Programming Exercises

(None for now)

II. Knowledge Summary

Core Idea

The Pigeonhole Principle, also known as the drawer principle, is one of the simplest yet most powerful tools in combinatorics. Its core idea is extremely straightforward: if more than n objects are placed into n containers, then at least one container must contain at least two objects. Although simple, it can solve many contest problems that initially seem to have no obvious direction.

Theorem Statement

Basic form: if n+1 objects are put into n containers, then at least one container contains at least 2 objects.

General form: if n objects are put into k containers, then at least one container contains at least ⌈n/k⌉ objects.

Strengthened form: if n₁ + n₂ + ... + nₖ - k + 1 objects are put into k containers, then there exists some i such that the i-th container contains at least nᵢ objects.

Reverse usage: if each container can hold at most m objects, then k containers can hold at most mk objects. If the number of objects exceeds mk, then it is impossible for every container to hold at most m objects.

Classic Problems and Proofs

Problem 1: Among any 13 people, at least 2 have birthdays in the same month.

Proof: there are 12 months (containers) and 13 people (objects). Since 13 > 12, by the pigeonhole principle at least 2 people share a birth month.

Problem 2: Among any n+1 integers chosen from 1 to 2n, there are two that are coprime.

Proof: split 1..2n into n groups: {1,2}, {3,4}, {5,6}, ..., {2n-1,2n}. Choose n+1 numbers. By the pigeonhole principle, at least two fall into the same group. Those two numbers are consecutive, so their gcd is 1.

Problem 3: Among any n+1 integers chosen from 1 to 2n, one of them divides another.

Proof: every positive integer can be uniquely written as 2^a × b, where b is odd. There are exactly n odd numbers in 1..2n: 1, 3, 5, ..., 2n-1. The odd part of every chosen number must be one of these n values. Choosing n+1 numbers forces two of them to have the same odd part b. Suppose they are 2^a1 × b and 2^a2 × b; if a1 < a2, then the former divides the latter.

Problem 4: Any 5 points inside a square of side length 1 must contain two points whose distance is at most √2 / 2.

Proof: divide the square into 4 smaller squares of side length 1/2. Put 5 points into these 4 small squares. By the pigeonhole principle, at least 2 points lie in the same small square. The diagonal length of a small square is √2 / 2, so the distance between those two points is at most √2 / 2.

Code Implementation

1#include <iostream>
2#include <vector>
3using namespace std;
4
5// Find the duplicate number among n+1 integers with values in [1, n]
6// The pigeonhole principle guarantees that a duplicate exists
7// Floyd's cycle detection: O(n) time, O(1) extra space
8int findDuplicate(vector<int>& nums) {
9    // View the array as a linked list: i -> nums[i]
10    // By the pigeonhole principle, a duplicate value implies a cycle
11    int slow = nums[0];
12    int fast = nums[nums[0]];
13
14    while (slow != fast) {
15        slow = nums[slow];
16        fast = nums[nums[fast]];
17    }
18
19    slow = 0;
20    while (slow != fast) {
21        slow = nums[slow];
22        fast = nums[fast];
23    }
24
25    return slow;
26}
27
28int main() {
29    int n;
30    cin >> n;
31    vector<int> nums(n + 1);
32    for (int i = 0; i <= n; i++) {
33        cin >> nums[i];
34    }
35    cout << "The duplicate number is: " << findDuplicate(nums) << endl;
36    return 0;
37}

1#include <iostream>
2#include <vector>
3using namespace std;
4
5// Given n positive integers, prove and find a consecutive subsequence whose sum is divisible by n
6void findDivisibleSubsequence(vector<int>& a, int n) {
7    // Prefix sums s[0]=0, s[1]=a[0], s[2]=a[0]+a[1], ...
8    // There are n+1 prefix sums, but only n possible remainders modulo n
9    // By the pigeonhole principle, at least two prefix sums have the same remainder
10    vector<int> prefix(n + 1, 0);
11    vector<int> seen(n, -1);
12
13    seen[0] = 0;
14    for (int i = 1; i <= n; i++) {
15        prefix[i] = prefix[i - 1] + a[i - 1];
16        int r = ((prefix[i] % n) + n) % n;
17
18        if (seen[r] != -1) {
19            int l = seen[r];
20            cout << "The sum of subsequence a[" << l + 1 << ".." << i << "] is "
21                 << prefix[i] - prefix[l]
22                 << ", which is divisible by " << n << endl;
23            return;
24        }
25        seen[r] = i;
26    }
27}
28
29int main() {
30    int n;
31    cin >> n;
32    vector<int> a(n);
33    for (int i = 0; i < n; i++) cin >> a[i];
34    findDivisibleSubsequence(a, n);
35    return 0;
36}

Application Example

Example: Given 5 integers 3, 7, 11, 15, 20, prove and find a consecutive subsequence whose sum is divisible by 5.

Prefix sums: s[0]=0, s[1]=3, s[2]=10, s[3]=21, s[4]=36, s[5]=56

Modulo 5: 0, 3, 0, 1, 1, 1

Since s[0] and s[2] are both 0 modulo 5, the subsequence a[1]+a[2] = 3+7 = 10 is divisible by 5.

Or since s[3] and s[4] are both 1 modulo 5, the subsequence a[4] = 15 is divisible by 5.

Detailed Problem-Solving Steps

1. Identify the "pigeons" and the "holes": determine what the objects are and what the containers are
2. Construct the classification: this is the most critical and skillful step; the "holes" must be designed carefully according to the problem
3. Compare the counts: if the number of objects exceeds the total allowed capacity of the containers, then some container must exceed its capacity
4. Draw the conclusion: the elements in the same "hole" must satisfy a common property

Common ways to construct "holes":

• By modulo classification
• By interval partition
• By geometric region partition
• By grouping according to some attribute, such as the same odd part

Common Mistakes

1. Failing to identify the "pigeons" and "holes", which makes the problem impossible to model
2. Counting the number of "holes" incorrectly
3. Remembering only the basic form and forgetting the general form
4. Confusing "existence proof" with "constructive solution" — the pigeonhole principle usually proves existence, not the concrete object directly
5. In programming problems, after using the principle to prove existence, forgetting to actually locate the solution

Summary

The charm of the pigeonhole principle lies in:

• Simplicity: the theorem itself is extremely simple
• Wide applicability: it appears in number theory, geometry, graph theory, analysis, and more
• Skillfulness: the hard part is not the theorem itself, but how to cleverly construct the "holes"

In contests, the pigeonhole principle is often used for:

• Existence proofs
• Prefix sum + modulo problems for finding consecutive subsequences
• Distance bounds in geometry
• Divisibility relations in number theory

The key to mastering the pigeonhole principle is to practice many different problem types until you develop the instinct to think of it whenever you see a counting relationship.