Pigeon-hole principle

This is one of those tricks that is "obvious" but turns out to be incredibly useful in proving things.

Fun fact: I was a TA for Elaine once!
Sarada has bunch of fun math videos-- check them out!
We also use the fact that every h_i is an integer and h_i>= 0 for every i in [n].

Background

This is another trick that you might not have seen formally before but it formalizes something pretty obvious (and turns out to be pretty useful too). Let us start with the most common instantiation of this principle:

Exercise 1

Consider any assignment of $n+1$ pigeons to $n$ holes. Then there exists at least one hole with at least $2$ pigeons in it.

The Proof

Next, we prove the above with a proof by contradiction.

Proof Idea

We will prove Exercise 1 with a proof by contradiction. We will assume that all holes have at most one pigeon in them and then conclude that there are at most $n$ pigeons.

Proof Details

For notational convenience, let $h_i$ denote the number of pigeons in the $i$th hole for every $i\in [n]$. For the sake of contradiction, let us assume that $h_i\le 1$ for every $i\in [n]$. Now since each pigeon is assigned to some hole, the total number of pigeons is \[\sum_{i=1}^n h_i \le \sum_{i=1}^n 1 =n,\] where the inequality follows from our assumption that $h_i\le 1$ for every $i\in [n]$. This implies that the total number of pigeons is at most $n$, which is a contradiction since there are $n+1$ pigeons. This implies1 that there exists at least one $i\in [n]$ such that $h_i\ge 2$, as desired.

In fact, one can modify the proof above to obtain the more general version (proof is left as an exercise):

Exercise 2

Consider any assignment of $m$ pigeons to $n$ holes, Then there exists at least one hole with at least $\left\lceil \frac{m}{n}\right\rceil$ pigeons in it.

Finally, one can prove the "converse" of the pigeon-hole principle above (again the proof is left as an exercise):

Exercise 3

Consider any assignment of $m$ pigeons to $n$ holes. Then there exists at least one hole with at most $\left\lfloor \frac{m}{n}\right\rfloor$ pigeons in it.

An Application

We now see how we can use the pigeon-hole principle to prove another statement:

Exercise 4

Consider a matching between $n$ men and $n$ women. If a man (or woman resp.) is not matched then there must exist a woman (man resp.) who is also not matched.

Proof Idea

We will prove the above by the pigeon-hole principle (Exercise 3). Let us consider the case when a woman is not matched-- then the matched women will be the pigeons and all the men will be the holes. Then we will conclude that there is at least one man who is not matched.

Proof Details

We will prove the case when there is an unmatched woman (and we have to show that there exists an unmatched man). The proof for the case when there is an unmatched man is similar and is omitted.

Let $w$ be the number of matched women. Note that since there is at least one woman who is not matched, we have $w\le n-1$. Now think of each of the $w$ woman to be a pigeon and the $n$ men to be the $n$ holes. The assignment of the pigeon to the holes is obvious: every matched woman is assigned to a unique man. Then by Exercise 3, there is one hole with at most $\left \lfloor \frac{w}{n}\right\rfloor \le \left\lfloor \frac{n-1}{n}\right\rfloor =0$ pigeons in it. This means that there is a man who is not assigned any woman, i.e. he is unmatched, as desired.

Further Resources

Below are some videos that go over the pigeonhole principle and talk about more applications.

Notation Switch!

Please note that the videos below use slightly different notation from above!

The first one is from Elaine Rich :2

Here is another one by Sarada Herke : 3