The Pigeonhole Principle

Introduction

Have you ever wondered how something as simple as fitting pigeons into pigeonholes can lead to profound mathematical insights?
The Pigeonhole Principle might seem straightforward at first glance, but its applications can be surprisingly deep and far-reaching.

In this post, we’ll explore what the pigeonhole principle is, delve into fascinating examples, and see how this principle helps solve complex problems in mathematics.

What Is the Pigeonhole Principle?

The pigeonhole principle is a simple yet powerful concept in combinatorics.
It states that if you have more pigeons than pigeonholes, at least one pigeonhole must contain more than one pigeon.

Formally, if items are put into containers, with , then at least one container must hold more than one item.

Simple Examples to Illustrate the Principle

Socks in a Drawer

Imagine you have 10 pairs of socks, each pair a different color, mixed together in a drawer.
If you pull out 11 individual socks, at least one pair of socks will match.

This happens because you have more socks (11) than the number of colors (10), guaranteeing a match.

Birthdays in a Group

Consider a group of 13 people. According to the pigeonhole principle, at least two people will share a birth month.
There are only 12 months in the year, so having 13 people ensures that one month must accommodate at least two birthdays.

A More Complex Example

This insightful approach is discussed in The Art and Craft of Problem Solving by Paul Zeitz.
Solving most pigeonhole problems involves a few key steps:

  1. Recognize that the problem might require the pigeonhole principle.
  2. Identify what the pigeons and holes represent — this is often the crux of the problem.
  3. Understand that applying the principle may not directly finish the problem — sometimes it only gives a key intermediate result.

The best problem solvers know when and how to use this reasoning.

Problem

Show that among any positive integers, there must be two whose difference is a multiple of .

Solution

  1. Consider the positive integers:

  2. Compute the remainders of these integers when divided by .
    Let the remainders be:

    where each remainder satisfies .

  3. Since there are remainders but only possible values (from to ), by the pigeonhole principle, at least two of these remainders must be the same.

  4. Let these integers be and with the same remainder .
    Therefore,

  5. This implies that

    for some integer .

Hence, we’ve shown that among any positive integers, there are at least two whose difference is a multiple of .

Conclusion

The pigeonhole principle may sound simple, but its power lies in its universality.
From probability puzzles to number theory and beyond, it appears in countless mathematical contexts — often as the hidden insight that unlocks a problem’s structure.

Next time you face a tricky problem, remember: sometimes it’s just about finding the right “pigeonholes.”