Course contentsShow
← Mathematics
Lesson 2570 of 3,12151. Discrete Math — Sets, Relations, FunctionsFree lesson

The Pigeonhole Principle: Statement and Intuition

Understanding the basic statement: if n+1 items are placed in n containers, at least one container has multiple items.

The Pigeonhole Principle: Statement and Intuition

What You'll Learn

You'll understand why stuffing more items than containers guarantees at least one container must hold multiple items—a surprisingly powerful counting principle.

The Basic Idea

The Pigeonhole Principle is deceptively simple: if you have n + 1 or more items to distribute among n containers (pigeonholes), then at least one container must contain two or more items.

Why? Suppose every container held at most one item. Then you could place at most n items total. But you have n + 1 items! This contradiction means our assumption was wrong—some container must hold multiple items.

Intuitive Examples

Birthdays in a room: If 13 people are in a room, at least two share a birth month. Why? There are only 12 months (containers) but 13 people (items). By the pigeonhole principle, some month must contain at least two birthdays.

Socks in a drawer: You have 10 pairs of socks (5 black, 5 blue) mixed randomly. If you grab 3 socks in the dark, must you have a matching pair? Yes! You have 3 socks (items) but only 2 colors (containers), so at least two socks must share the same color.

The Formal Statement

Pigeonhole Principle: Let n be a positive integer. If n + 1 or more objects are placed into n boxes, then at least one box contains two or more objects.

This connects directly to functions: if you have a function from a set with n + 1 elements to a set with n elements, the function cannot be injective (one-to-one)—some element in the codomain must have at least two pre-images.

Key Takeaway: The Pigeonhole Principle guarantees that distributing n + 1 items into n containers forces at least one container to hold multiple items—a fundamental counting argument with surprising applications.