The Pigeonhole Principle

If n+1 pigeons fly into n holes, at least one hole has 2+ pigeons

Welcome to the Pigeonhole Principle!

The Pigeonhole Principle is one of the simplest yet most powerful proof techniques in mathematics. The basic idea is almost trivial: if you have more pigeons than pigeonholes, at least one hole must contain multiple pigeons. Despite its simplicity, this principle underlies surprising results in combinatorics, number theory, and computer science.

What You'll Learn

1

Basic Principle

Understand the fundamental counting argument with interactive dragging

2

Generalized Form

Explore the extended principle: kn+1 objects guarantee k+1 in one container

3

Classic Applications

Solve famous problems by identifying the "pigeons" and "holes"

4

Proof Structure

Walk through a formal proof by contradiction step-by-step

Basic Pigeonhole Demo

Drag the pigeons into the holes. When you have more pigeons than holes, at least one hole must contain 2+ pigeons!

5
4
You have 5 pigeons and 4 holes. Since 5 > 4, the pigeonhole principle guarantees at least one hole will have 2+ pigeons. Try placing all pigeons!

Key Insight

If n+1 objects are placed into n containers, at least one container must hold more than one object. This simple fact is surprisingly powerful in mathematics!

Formal Statement

Basic Pigeonhole Principle:

If n+1 objects are distributed among n containers, then at least one container must contain more than one object.

Equivalently: If we map n+1 elements to n elements, the mapping cannot be injective (one-to-one). At least two elements must map to the same target.

Generalized Pigeonhole Principle

If kn+1 objects are placed into n boxes, at least one box contains k+1 or more objects.

Objects needed = k × n + 1 = 2 × 4 + 1 = 9
Guarantees at least one box has 3+ objects
4
2
Objects placed: 0 / 9Max in any box: 0

Generalized Form

If kn+1 objects are distributed among n containers, at least one container must hold at least k+1 objects. This generalizes the basic principle (where k=1).

Classic Applications

Practice identifying the "pigeons" and "holes" in famous problems. This skill is key to applying the principle!

Matching Socks

easy

A drawer contains socks of 2 different colors (black and white). What is the minimum number of socks you must draw (without looking) to guarantee you have at least 2 socks of the same color?

Proof Walkthrough

Follow the step-by-step proof by contradiction. Expand each step to understand the reasoning.

We have n+1 objects (pigeons) and n containers (pigeonholes). We want to prove that at least one container must hold more than one object.

Proof Technique: Contradiction

This proof uses proof by contradiction: we assume the opposite of what we want to prove, then show this leads to an impossibility. Since the assumption causes a contradiction, it must be false, proving our original claim.

Key Takeaways

  • 1.The Pigeonhole Principle proves existence without construction - we know something must exist, but we don't know which specific object.
  • 2.The key to applying the principle is correctly identifying what the "pigeons" and "holes" represent in your problem.
  • 3.The generalized form (kn+1 objects in n containers gives k+1 in one) extends the basic principle to guarantee multiple collisions.
  • 4.Many "impossible" sounding problems become trivial once you find the right pigeonhole formulation.