Pigeon Hole Principle Mathematical Preliminaries Part 3

Pigeon Hole Principle

If n+1 or more objects are placed into n boxes, then there is at least one box containing two or more objects. In other words, if A and B  are two sets such that |A| > |B|, then there is no one-to-one function from A to B.

Theorem 1: Let n be a positive integer. Every sequence of n² + 1 distinct real numbers contains a subsequence of length n+1 that is either increasing or decreasing.

Proof. For example consider the sequence (20, 10, 9, 7, 11, 2, 21, 1, 20, 31) of 10 = 3² + 1 numbers. This sequence contains an increasing subsequence of length 4 = 3 + 1, namely (10, 11, 21, 31).

The proof of this theorem is by contradiction, and uses the pigeon hole principle.

Let (a₁, a₂,…..,a_n²+1) be an arbitrary sequence of n² + 1 distinct real numbers. For each i with 1 ≤ i ≤ n² + 1, let inc_i denote the length of the longest increasing subsequence that starts at a_i, and let dec_i denote the length of the longest decreasing subsequence that starts at a_i
Using this notation, the claim in the theorem can be formulated as follows:

There is an index i such that inc_i ≥ n + 1 or dec_i ≥ n + 1.

We will prove the claim by contradiction. So we assume that inc_i ≤ n and dec_i ≤ n for all i with 1 ≤ i ≤ n² + 1.
Consider a set

B = {(b,c): 1 ≤ b ≤ n, 1 ≤ c ≤n },
and think of the elements of B as being boxes. For each i with 1 ≤ i ≤ n² + 1, the pair (inc_i, dec_i) is an element of B. So we have n² + 1 elements (inc_i, dec_i), which are placed in the n² boxes of B. By the pigeon hole principle, there must be a box that contains two (or more) elements. In other words, there exist two integers i and j and

(inc_i,dec_i) = (inc_j,dec_j).
Recall that the elements in the sequence are distinct. Hence, a_i ≠ a_j. We consider two cases.
First assume that a_i < a_j . Then the length of the longest increasing subsequence starting at a_i must be at least 1 + inc_j, because we can append a_i to the longest increasing subsequence starting at a_j. Therefore, inc_i ≠ inc_j which is a contradiction.
The second case is when a_i > a_j. Then the length of the longest decreasing subsequence starting at a_i must be at least 1 + dec_j, because we can append a_i to the longest decreasing subsequence starting with a_j. Therefore, dec_i ≠ dec_j, which is again a contradiction.