Course contentsShow
← Computer Science
Lesson 103 of 2,8722. Discrete Mathematics for CSFree lesson

The Pigeonhole Principle

Understand why distributing n+1 objects into n boxes guarantees at least one box contains multiple objects.

The Pigeonhole Principle

What you'll learn: Why cramming more items than containers guarantees overlap — a surprisingly powerful counting insight.

The Core Idea

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

Think about it: you have 11 emails to sort into 10 folders. Even if you try to spread them out perfectly, you'll run out of folders before you run out of emails. Some folder has to hold at least two emails.

Why It Works

This isn't magic — it's basic arithmetic. Suppose you try to avoid putting multiple objects in any box. The maximum you could distribute is exactly n objects (one per box). But you have n+1 objects. That extra object has nowhere to go except into a box that already contains something.

Everyday Examples

  • 13 people in a room: At least two share the same birth month (12 months, 13 people).
  • 367 people: At least two share the same birthday (366 possible days including leap day).
  • Usernames: If you have 1,001 users and only 1,000 available usernames, at least two users must share a username pattern (collision inevitable).

In Computer Science

This principle underlies hash collisions, proof techniques, and algorithm analysis. When analyzing storage limits, network packet IDs, or memory addresses, the Pigeonhole Principle guarantees certain overlaps are unavoidable.

Key Takeaway: If n+1 items are distributed into n containers, at least one container must hold multiple items — a simple yet powerful guarantee used throughout CS proofs and algorithm design.