The Essence of the Pigeonhole Principle

Surprisingly, this powerful logical tool is often overlooked in early mathematical education, despite being accessible to those with minimal math experience. The principle can be summarized simply:

“If n items are placed into m containers where n > m, then at least one container must hold more than one item.”

Isn’t that astonishing? Yes, it is that straightforward! Yet, as we will soon discover, this principle can lead to remarkable and often unexpected conclusions.

The name originates from the visual of pigeons needing to fit into pigeonholes—when there are more pigeons than holes, at least one hole must contain more than one pigeon.

We can refine this principle further:

“If n items are distributed among m containers with n > m, then at least one container will have at least ⌈n/m⌉ items.”

Here, the notation ⌈n/m⌉ denotes the ceiling function, which rounds up to the nearest integer. For example, if there are 22 pigeons and 3 pigeonholes, at least one hole must contain ⌈22/3⌉ = 8 pigeons. This is the quantified version of the Pigeonhole Principle.

Hairy Twins

Let’s apply our newfound knowledge by proving that in London, there exist at least two individuals with the same number of hairs on their heads.

At first glance, this statement may appear daunting; after all, how could we possibly survey every person in London? However, we can elegantly prove it with a simple logical argument rooted in the Pigeonhole Principle.

We can disregard bald individuals, as they would make the problem trivial. On average, a human has about 150,000 hairs, and it’s reasonable to assume that no one exceeds 1 million hairs. Given that London's population is over 1 million, the Pigeonhole Principle guarantees that at least two people must share the same hair count.

Using the quantified version, we can assert that at least 9 individuals in London have the same number of hairs on their heads. In this scenario, the number of hairs acts as the pigeonholes, while the Londoners are the pigeons.

This argument is applicable to numerous other populations beyond just London!

Five Points on a Sphere

Regardless of how five points are arranged on a sphere, I can always find a closed hemisphere that contains at least four of them. Here, "closed" means that if a point lies on the boundary, it is considered included.

The Pigeonhole Principle already indicates that the five points must be allocated between two non-overlapping hemispheres, ensuring that at least three will reside in one of them. If we choose the hemispheres after placing the points, we can cleverly select two points and draw a great circle through them. The remaining three points must then conform to the Pigeonhole Principle, ensuring that two will fall within the same hemisphere.

This concept implies that if you select five locations you’ve visited on Earth, at least four will be situated within the same hemisphere! Fascinatingly, this principle also applies to celestial bodies like the Moon or Mars.

The first video, "The Pigeon Hole Principle: 7 Gorgeous Proofs", explores various proofs that exemplify the beauty of this principle and its applications.

Repeating Decimal Patterns

Most people are aware that fractions of integers or rational numbers exhibit repeating decimal patterns, but few understand why.

A straightforward explanation involves long division. When dividing n by m, each step generates a new remainder between 0 and m-1, leading to the next digit in the decimal representation. After m iterations, the Pigeonhole Principle implies that at least one remainder must repeat, resulting in a loop of digits that continues indefinitely.

An intriguing exercise for readers: why does a decimal with a repeating sequence necessarily indicate that it is a rational number?

Tiling a Chessboard with Dominoes

Imagine a chessboard from which two opposite corners (e.g., squares a1 and h8) have been removed, leaving 62 squares. Can we cover this board entirely with 1 × 2 dominoes?

Initially, this may seem complex. Since there are 32 white squares and a domino covers one black and one white square, we would need 32 dominoes to cover 64 squares. However, with only 62 squares remaining, the Pigeonhole Principle confirms that at least one square must be covered more than once, thus making tiling impossible.

The Impossibility of Perfect Compression Algorithms

Compression algorithms are programs designed to reduce the size of data files, such as documents or images. There are two types: lossless compression, which perfectly reconstructs the original data, and lossy compression, which produces a similar yet not identical version.

The question arises: is there a compression algorithm that can compress any data? The answer is no. If such an algorithm existed, it would take longer strings of bits and produce shorter ones. However, since there are more possible longer strings than shorter ones, the Pigeonhole Principle implies that some strings would inevitably compress into the same shorter string, which contradicts the assumption of losslessness.

Consequently, lossless algorithms may expand some data while compressing others.

Algorithmic Cycles on a Rubik’s Cube

In the context of a Rubik’s Cube, an algorithm refers to a series of moves. Importantly, these moves are reversible. If you start with a solved cube and repeatedly apply the same algorithm, you will eventually return to the original state.

The reasoning is straightforward: there are more possible applications of the algorithm than distinct configurations of the cube. As each application alters the configuration, the Pigeonhole Principle ensures that eventually, the cube will revert to a previous configuration.

Moreover, if the cube reaches a configuration between the starting and current states, it would imply that the same state could be attained from two different configurations—a contradiction, as algorithms are reversible. Thus, each algorithm segments the cube's configurations into distinct cycles.

To put it in perspective, there are approximately 43 quintillion configurations of the Rubik's Cube!

Handshaking at Parties

At any gathering where handshaking occurs, there will always be at least two participants who shake hands with the same number of individuals.

This proof requires a bit more finesse. Let’s say there are N+1 attendees. A person can shake hands with anywhere from 0 to N others. If one person shakes hands with no one, then no one can shake hands with everyone else, and vice versa.

Thus, the possible handshakes can either range from {0, 1, 2, …, N-1} or {1, 2, …, N}. Regardless of the situation, there are still N possible handshakes and N+1 guests, ensuring at least two guests shake hands with the same number of attendees.

Exploring Sums of Random Numbers

If you randomly select 10 two-digit numbers, there will always be two non-empty, non-overlapping subsets that sum to the same total.

The smallest possible sum is 10 (using the smallest two-digit number), while the maximum occurs with the nine largest two-digit numbers, resulting in a sum of 855. This gives us 846 distinct sums.

For 10 chosen numbers, each can either be included in a collection or not, resulting in 2¹⁰ = 1024 potential collections. Excluding the empty and full collections leaves us with 1022 feasible subsets.

With 1022 collections and only 846 sums available, the Pigeonhole Principle guarantees that at least two collections will yield the same sum. If two collections share a number, we can remove it from both while maintaining their sums—this process can be repeated until the collections are disjoint.

For an advanced challenge, consider this: if 101 natural numbers are evenly distributed on a circle with a total sum of 300, there will always be a contiguous arc of numbers whose sum equals 200.