Pigeonhole principle

The pigeonhole principle is a classic counting technique in mathematics and combinatorics. It states that if you have more elements than boxes to put them in, then at least one box must contain more than one element.

 

The principle is surprisingly simple, but very powerful. It is used to prove that certain situations are unavoidable, no matter how the elements are distributed. There is a simple and a general version.

 

 

Simple pigeonhole principle

If you have k + 1 elements to be distributed in k boxes, then at least one box will contain more than one element.

 

Example 1: Birthdays

In a group of 13 people, at least two must have their birthday in the same month, since there are only 12 months.

 

Example 2: Socks

If you have 3 socks but only 2 colors (e.g. black and white), then at least two socks will have the same color.

 

Proof (simple)

Assume the opposite: that no box contains more than one element. Then there can be at most k elements in k boxes. But we have k + 1 elements. This is a contradiction, and therefore at least one box must have more than one element.

 

 

General pigeonhole principle

If you distribute N elements in k boxes, at least one box will contain at least:

 

$$ \large \left\lceil \frac{N}{k} \right\rceil $$

 

This means that you can always guarantee a certain minimum distribution, no matter how the elements are placed.

 

 

Example 1: Football match

There are 40,000 spectators at a match and 365 possible birthdays. At least one birthday is shared by:

 

$$ \large \left\lceil \frac{40000}{365} \right\rceil = 110 $$

 

This means that at least 110 people share a birthday.

 

 

Example 2: Card game

In a deck of 52 cards without jokers, the cards are divided into 4 suits. If you draw 21 cards, then at least one suit will have:

 

$$ \large \left\lceil \frac{21}{4} \right\rceil = 6 $$

 

So you are guaranteed to have at least 6 cards in the same suit.

 

 

Proof (general)

If all boxes had at most \( \large \left\lfloor \frac{N}{k} \right\rfloor \) elements, then the total number of elements would be at most \( \large k \cdot \left\lfloor \frac{N}{k} \right\rfloor \leq N \). But if this were the case, there would not be enough room for some elements. Therefore at least one box must have \( \large \left\lceil \frac{N}{k} \right\rceil \) elements.

 

 

Applications

The pigeonhole principle seems simple, but it is used in many advanced contexts:

 

• Combinatorics: Proofs about permutations and combinations.
• Probability: Showing that certain outcomes are unavoidable.
• Graph theory: Guaranteeing that a graph has nodes with specific connections.
• Computer science: Hash functions and data storage – if you have more elements than slots, collisions must occur.

 

 

Summary

The pigeonhole principle states that if you have more elements than boxes, then at least one box must contain more than one element. The general version gives us the formula:

 

$$ \large \left\lceil \frac{N}{k} \right\rceil $$

 

The principle can be proven simply, but it has deep applications in mathematics and computer science. It ensures that we can understand when something is unavoidable, and it is an important tool in combinatorics and probability.