## Section4.1The 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.