The Pigeonhole Principle: An Introduction

The Principle: So Simple, It's Obvious

The Pigeonhole Principle, sometimes called Dirichlet's Box Principle, states that if you have more items than you have containers, at least one container must hold more than one item.

Formally, if you place $n+1$ items (pigeons) into $n$ containers (pigeonholes), then at least one pigeonhole must contain at least two pigeons.

The core of any pigeonhole argument is correctly identifying three things:

1. The pigeons (the items being distributed).
2. The pigeonholes (the categories or boxes the items are placed into).
3. The rule for placing a pigeon into a pigeonhole.

Let's watch a short video that provides a clear, visual introduction to this idea.

Basic Applications: Making It Concrete

The power of the Pigeonhole Principle lies in its application. The challenge is rarely in understanding the principle itself, but in structuring a problem so the principle can be applied. Let's start with a classic example.

Problem: In any group of 13 people, must at least two of them share a birthday month?

• Pigeons: The 13 people. ($n=13$)
• Pigeonholes: The 12 months of the year. ($m=12$)
• Rule: Assign each person (pigeon) to the month (pigeonhole) of their birthday.

Since we have more pigeons (13) than pigeonholes (12), the principle guarantees that at least one pigeonhole (month) must contain at least two pigeons (people). Thus, at least two people must share a birthday month.

Now, let's apply this to a context you're comfortable with: number theory.

The solution you just read demonstrates a typical pigeonhole argument in number theory. The key was to categorize the integers by their parity.

• Pigeons: The 3 integers.
• Pigeonholes: The two possible remainders when divided by 2 (i.e., parity): {Even (remainder 0), Odd (remainder 1)}.
• Rule: Place each integer into the pigeonhole corresponding to its parity.

With 3 pigeons and only 2 pigeonholes, two of the integers must end up in the same pigeonhole—meaning they have the same parity. The sum of two even numbers is even, and the sum of two odd numbers is even. In either case, our conclusion holds.

Crafting Clever Pigeonholes

The most elegant applications of the PHP involve a clever choice of pigeonholes that isn't immediately obvious. This is where the problem-solving artistry begins.

Let's look at a problem where we must construct the categories ourselves.

As you saw, the crucial insight was to define the pigeonholes not as individual numbers, but as pairs of numbers that satisfy the desired property (summing to 9):

• Pigeonholes: The four sets: $\{1,8\},\{2,7\},\{3,6\},\{4,5\}$.
• Pigeons: The five numbers chosen from the set $\{1,2,...,8\}$.
• Rule: Place a chosen number into the set that contains it.

Since we choose 5 numbers (pigeons) and there are only 4 sets (pigeonholes), two of the chosen numbers must belong to the same set. By construction, any two distinct numbers in the same set sum to 9. This proves the claim.

A More Abstract Application: The Handshake Problem

The Pigeonhole Principle isn't limited to numbers and physical objects. It can be applied to abstract properties and relationships. A famous example is the handshake problem.

Let's break down the logic for a group of $n$ people:

• Pigeons: The $n$ people at the party.
• Pigeonholes: The possible number of hands a person can shake.

A person can shake hands with anyone from 0 people to all $n-1$ other people. So, the possible values are $\{0,1,2,\dots ,n-1\}$. At first, this seems like $n$ possible values, giving us $n$ pigeonholes for $n$ pigeons, which isn't enough to apply the principle.

However, the solution reveals the key insight: it is impossible for a person who shook 0 hands (a "loner") and a person who shook $n-1$ hands (shook hands with everyone else) to coexist in the same group. If the "loner" exists, the maximum number of handshakes anyone could have is $n-2$. If the "social butterfly" exists, the minimum number of handshakes anyone could have is 1.

Therefore, the set of actual handshake counts must be a subset of either $\{0,1,\dots ,n-2\}$ or $\{1,2,\dots ,n-1\}$. Both of these sets have size $n-1$. We now have $n$ people (pigeons) and at most $n-1$ possible handshake counts (pigeonholes). By the PHP, at least two people must have shaken the same number of hands.

Practice Problems

Now it's time to apply what you've learned. For each problem, your first step should always be to clearly define your pigeons and pigeonholes.

1. Socks in the Dark: You have a drawer with many socks, all identical except for their color. There are black socks, white socks, and blue socks. You are pulling socks out in the dark. How many socks must you pull to guarantee you have a matching pair?

2. Geometric Dots: Five points are placed inside an equilateral triangle of side length 1. Prove that at least two of the points are within $\frac{1}{2}$ unit of distance from each other.

   • Hint: How can you divide the triangle into regions such that any two points within the same region are guaranteed to be close enough?

3. Picking Numbers: Prove that if you select 11 distinct integers from the set $\{1,2,\dots ,20\}$, there must be a pair of selected integers such that one divides the other.

   • Hint: This is a classic, difficult problem. Every integer $x$ can be written uniquely as $x=2^k\cdot m$, where $m$ is an odd number. What are the pigeons? What property of these numbers could serve as the pigeonholes?

Conclusion

Today we introduced the Pigeonhole Principle, a simple concept that provides a rigorous way to prove existence. We've seen how its power is unlocked by correctly identifying the "pigeons" and "pigeonholes," sometimes in very creative ways. We've applied it to simple distribution scenarios, number theory problems, and more abstract structural questions.

Key Takeaways:

• The Pigeonhole Principle states that if $n+1$ items are placed into $n$ boxes, at least one box must contain two or more items.
• The primary challenge is modeling a problem by defining the pigeons (items) and pigeonholes (categories).
• The pigeonholes can be abstract concepts like parity, pairs of numbers summing to a constant, or the number of handshakes.

In our next lesson, we will explore the Generalized Pigeonhole Principle. This extension will allow us to prove more powerful results, such as guaranteeing that at least three items must be in the same box, or calculating the minimum number of items needed to ensure a certain group size.