Pigeonhole Principle

Definition

The Pigeonhole Principle

If n + 1 (or more) objects are placed into n boxes, then at least one box contains two or more objects.

More generally: if N objects are placed into k boxes, then at least one box contains ⌈N/k⌉ objects (where ⌈ ⌉ is the ceiling function).

Example

Simple Application

In any group of 13 people, at least 2 share the same birth month.

Reasoning: There are 12 months (boxes) and 13 people (objects). By the pigeonhole principle, at least one month contains ⌈13/12⌉ = 2 people.

Example

Sock Problem

A drawer has 10 red socks and 10 blue socks (all mixed up). How many socks must you draw (in the dark) to guarantee a matching pair?

2 colors (boxes), so you need 2 + 1 = 3 socks. The first two might be different colors, but the third must match one of them.

Example

Integers and Remainders

Prove: Among any 5 integers, two have the same remainder when divided by 4.

There are 4 possible remainders: 0, 1, 2, 3 (these are the "boxes"). We have 5 integers ("objects"). By the pigeonhole principle, at least two integers share the same remainder.

Note

The Art of Pigeonhole Proofs

The key challenge is identifying the right "pigeons" and "holes." The principle itself is simple, but choosing what to count and how to categorize is where the creativity lies. The pigeonhole principle only proves existence - it does not tell you which specific box has multiple items.