Skip to main content

Section 4.1 The Pigeon Hole Principle

A function \(f:X\longrightarrow Y\) is said to be \(1\)–\(1\) (read one-to-one) when \(f(x)\neq f(x')\) for all \(x,x'\in X\) with \(x\neq x'\text{.}\) A \(1\)–\(1\) function is also called an injection or we say that \(f\) is injective. When \(f:X\longrightarrow Y\) is \(1\)–\(1\text{,}\) we note that \(|X|\le |Y|\text{.}\) Conversely, we have the following self-evident statement, which is popularly called the “Pigeon Hole” principle.

In more casual language, if you must put \(n+1\) pigeons into \(n\) holes, then you must put two pigeons into the same hole.

Here is a classic result, whose proof follows immediately from the Pigeon Hole Principle.

Let \(\sigma=(x_1,x_2,x_3,\dots,x_{mn+1})\) be a sequence of \(mn+1\) distinct real numbers. For each \(i=1,2,\dots,mn+1\text{,}\) let \(a_i\) be the maximum number of terms in a increasing subsequence of \(\sigma\) with \(x_i\) the first term. Also, let \(b_i\) be the maximum number of terms in a decreasing subsequence of \(\sigma\) with \(x_i\) the last term. If there is some \(i\) for which \(a_i\ge m+1\text{,}\) then \(\sigma\) has an increasing subsequence of \(m+1\) terms. Conversely, if for some \(i\text{,}\) we have \(b_i\ge n+1\text{,}\) then we conclude that \(\sigma\) has a decreasing subsequence of \(n+1\) terms.

It remains to consider the case where \(a_i\le m\) and \(b_i\le n\) for all \(i=1,2,\dots,mn+1\text{.}\) Since there are \(mn\) ordered pairs of the form \((a,b)\) where \(1\le a\le m\) and \(1\le b\le n\text{,}\) we conclude from the Pigeon Hole principle that there must be integers \(i_1\) and \(i_2\) with \(1\le i_1\lt i_2\le mn+1\) for which \((a_{i_1},b_{i_1})=(a_{i_2},b_{i_2})\text{.}\) Since \(x_{i_1}\) and \(x_{i_2}\) are distinct, we either have \(x_{i_1}\lt x_{i_2}\) or \(x_{i_1}>x_{i_2}\text{.}\) In the first case, any increasing subsequence with \(x_{i_2}\) as its first term can be extended by prepending \(x_{i_1}\) at the start. This shows that \(a_{i_1}>a_{i_2}\text{.}\) In the second case, any decreasing sequence of with \(x_{i_1}\) as its last element can be extended by adding \(x_{i_2}\) at the very end. This shows \(b_{i_2}>b_{i_1}\text{.}\)

In Chapter 11, we will explore some powerful generalizations of the Pigeon Hole Principle. All these results have the flavor of the general assertion that total disarray is impossible.