Skip to content
Tutorials Center
My learning

Topics

Lesson 27 of 36 ยท Pigeonhole and Ramsey

The Pigeonhole Principle

Learn the pigeonhole principle and its generalized form, then prove classic results: divisible pairs among n+1 numbers and subset sums divisible by n, checked in Python.

If you put 11 pigeons into 10 holes, some hole contains at least two pigeons. That is the whole pigeonhole principle: when more objects than boxes, some box holds more than one. It sounds too obvious to be useful, yet it proves remarkable facts, because the work is in choosing the right boxes. The proofs are non-constructive: they show that something exists without saying where it is.

Statements

  • Basic form: if n + 1 or more objects are placed into n boxes, some box contains at least two objects.
  • Generalized form: if N objects go into k boxes, some box contains at least ceil(N/k) objects. With 100 people and 12 months, some month has at least ceil(100/12) = 9 birthdays.
  • Infinite form: if infinitely many objects go into finitely many boxes, some box gets infinitely many.

The recipe

  1. Identify the objects (the things you have many of).
  2. Design the boxes (a rule that sorts objects so that two in the same box have the property you want).
  3. Check that objects outnumber boxes.
  4. Conclude.

Example 1: a divisible pair

Choose any n + 1 numbers from {1, 2, ..., 2n}. Then two of them divide one another.

Write every number as 2^a * m with m odd. Boxes: the odd part m. There are only n odd numbers in 1..2n, so among n + 1 chosen numbers two share an odd part: 2^a m and 2^b m. The smaller divides the larger.

The result is sharp: you can pick n numbers with no divisible pair (take n+1, ..., 2n). The code below checks every subset for n up to 7 and also computes the largest "divisibility-free" subset.

Python Verify the divisible-pair theorem

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

For every n, always is True and the largest free subset has exactly n numbers. The last line shows the 10 boxes (odd parts) for n = 10.

Example 2: a block with sum divisible by n

Any n integers a_1, ..., a_n contain a consecutive block whose sum is divisible by n.

Form the prefix sums S_0 = 0, S_1 = a_1, S_2 = a_1 + a_2, ..., S_n. That is n + 1 numbers, but only n possible remainders mod n. Two prefix sums S_i and S_j (i < j) have the same remainder, so S_j - S_i = a_{i+1} + ... + a_j is divisible by n.

The proof is also an algorithm: scan, remember the first index at which each remainder appeared, and stop at the first repeat. That is how "subarray sum divisible by k" problems are solved in O(n).

Python Find the block and test it on random data

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

For the list 4, 6, 1, 9, 2, 8, 3 and n = 7, the block [6, 1] sums to 7. In 10,000 random trials the function always returns a valid block, as the principle guarantees.

flowchart LR
    A["n + 1 prefix sums"] --> B["sort into n remainder boxes"]
    B --> C["two share a box"]
    C --> D["their difference is a block with sum divisible by n"]

The boxes are the remainders; the pigeons are the prefix sums.

Other quick examples

  • Among any 13 people, two were born in the same month.
  • In any group of 2 or more people, two have the same number of friends in the group (friend counts lie in 0..n-1, but 0 and n-1 cannot both occur).
  • A hash table with more keys than slots must have a collision: the reason no hash function can be both short and injective.
  • Any lossless compressor that shortens some file must lengthen another: there are fewer short strings than long ones.

The principle only guarantees that some box is crowded. It never says which one, and it gives no way to find it without more work.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. A class has 40 students. What is the guaranteed minimum number of students sharing a birth month?

    ceil(40/12) = 4, so some month has at least 4 birthdays.
  2. 2. What are the boxes in the proof that n+1 numbers from 1..2n contain a divisible pair?

    There are n odd numbers up to 2n; two chosen numbers share an odd part and differ only by a power of 2.
  3. 3. In the block-sum proof, how many prefix sums (including S0) are used for n numbers?

    n + 1 prefix sums map into n remainders, so two coincide.
  4. 4. A pigeonhole proof usually tells you...

    Pigeonhole arguments are existence proofs.

Summary

  • n + 1 objects in n boxes: some box has two; generally some box has at least ceil(N/k).
  • The craft is choosing boxes: odd parts, remainders, colors, positions.
  • Divisible pair among n+1 numbers of 1..2n; block sum divisible by n; both bounds are tight.

Next: Pigeonhole Applications