The pigeon hole principle

This is a simple, obvious principle with surprisingly powerful consequences. The pigeon hole principle is something toddlers learn: if you put 3 blocks into 2 boxes, one box will end up with more than 1 block. Formally: if n+1 or more objects are placed into n boxes, then there is at least one box containing two or more objects.

Now that we know about sets and functions, we can also compose the definition in terms of set theory: if A and B are two sets such that |A| > |B|, then there is no one-to-one function from A to B.

Theorem 6. Let n be a positive integer. Every sequence of n^{2}+1 distinct real numbers contains a subsequence of length n+1 that is either increasing or decreasing.

Example: let’s take n = 3. A sequence of 3^{2}+1 distinct real numbers could look like so: (20, 10, 9, 7, 11, 2, 21, 1, 20, 31). According to the theorem 6, it must contain a subsequence of length 3+1 that is either increasing or decreasing. Look closely and, indeed, it does: (10, 11, 21, 31).

Proof. Let (a_{1}, a_{2}, \ldots ,a_{n^{2}+1}) be an arbitrary sequence of n^{2}+1 distinct real numbers. For each i with 1 \leq i \leq n^{2} + 1:

• let inc_{i} denote the length of the longest increasing subsequence that starts at a_{i}
• let dec_{i} denote the length of the longest decreasing subsequence that starts at a_{i}.

Let’s reformulate the theorem using this notation: there is an index i such that inc_{i} \geq n+1 or dec_{i} \geq n+1.

We will prove this claim by contradiction, using the pigeon hole principle. Recall that proof by contradiction starts with the negation (opposite) of the theorem’s claim. So, assume that inc_{i} \leq n and dec_{i} \leq n for all i with 1 \leq i \leq n^{2} + 1.

Now, consider the set:

B = \{ (b,c) : 1 \leq b \leq n, 1 \leq c \leq n \},

and think of elements of B as boxes. For each i with 1 \leq i \leq n^{2} + 1, the pair (inc_{i}, dec_{i}) is an element of B. So we have n^{2} + 1 such elements (inc_{i}, dec_{i}), but there are only n^{2} boxes in B. By the pigeon hole principle, there must be a box that contains two or more elements. So, there exists two integers i and j such that i < j and

(inc_{i}, dec_{i}) < (inc_{j}, dec_{j}).

Recall that the elements in the sequence are distinct (no repeating numbers). Hence, a_{i} \neq a_{j}. There are two cases then:

Case 1. a_{i} < a_{j}. Then the length of the longest increasing subsequence starting at a_{i} must be 1 + inc_{j}, because we can append a_{i} to the longest increasing subsequence starting from a_{j}. Therefore, inc_{i} \neq inc_{j}, which contradicts (1).

Case 2. a_{i} > a_{j}. Then the length of the longest deccreasing subsequence starting at a_{i} must be 1 + inc_{j}, because we can append a_{i} to the longest deccreasing subsequence starting from a_{j}. Therefore, dec_{i} \neq dec_{j}, which again contradicts (1). \blacksquare.