18.1.4. Pigeonhole Principle Application

Here we want to show the following that you take any sequence of n + 1 distinct real numbers. They are arbitrary real numbers; may be positive, negative in any order you take them. The only condition is that they have to be distinct. Then the claim is that irrespective of the n + 1 real numbers that you have in your sequence you always have a subsequence of length n + 1 which is either strictly increasing or strictly decreasing.

The problem begins by stating that we are considering a sequence of n + 1 distinct real numbers. These numbers can be any values, as long as they are not repeated. The key takeaway from the claim is that no matter how these numbers are arranged, there will be a subsequence consisting of n + 1 numbers that either increases or decreases throughout its length. This is a foundational concept in combinatorial mathematics and is often derived using the pigeonhole principle.

Think of a classroom with 11 students where each student's height is unique. No matter how you line them up, you can always find a group of 6 students who are either all increasing in height from left to right or all decreasing in height. It’s like trying to arrange your books on a shelf – you can’t escape creating one section that either goes from smallest to largest or largest to smallest.

First of all what is a strictly increasing sequence? A sequence of the form (a1, a2, ...) where a1 < a2 < a3 < ... . Whereas if I have a sequence of the form (b1, b2, ...) where b1 > b2 > b3 > ... then it is a strictly decreasing sequence.

A strictly increasing sequence is one in which each number is larger than the preceding number. Conversely, a strictly decreasing sequence is one in which each number is smaller than the preceding number. Understanding these definitions is crucial as it sets the stage for recognizing the required properties of the subsequence we will be discussing.

Consider climbing stairs: when you step on each stair, you're moving up, which forms a strictly increasing sequence of your height as you rise. Now if you were to descend the stairs, your height would decrease as you step down, creating a strictly decreasing sequence.

Now what does a subsequence mean? A subsequence means here that the values may not be consecutive. That means I am allowed to miss a few numbers.

A subsequence is derived from the original sequence by omitting some elements without changing the order of the remaining elements. For example, if we take the sequence {1, 3, 0, -5, 2, 8}, one possible subsequence could be {1, -5, 2}, which skips some numbers. This flexibility allows us to find the increasing or decreasing order required by the problem statement.

Imagine you are baking a cake and have a recipe that lists several ingredients in order. You don’t need to use all the ingredients; you can choose to skip some while still following the sequence of steps. Similarly, in our sequence, we can skip numbers but maintain their original order.

By that I mean that you have a set of n + 1 values going from left to right but need not be in consecutive locations; some of the locations might be skipped.

The crux of the problem lies in employing the pigeonhole principle, which states that if you have more items (pigeons) than containers (pigeonholes), at least one container must hold more than one item. In this case, the containers represent the potential lengths of sequences, which are limited due to our defined maximum length (n). This principle is what guarantees the existence of an increasing or decreasing subsequence of the required length.

Imagine you have 11 different colored balls (the n + 1 numbers) and only 10 boxes (the possible heights or position values). When you try to put each ball in a box, at least one box will end up with two balls, much like how the sequences will have some overlap in increases or decreases.

Assume that the statement is false and that means for each ai in the sequence, the value L_i is at most n.

To prove the existence of an increasing or decreasing subsequence of length n + 1, we start by assuming the opposite. If we presume that each ai produces a subsequence that is limited to a maximum length of n, we can analyze the implications of this assumption. This leads us into a contradiction, as shown through the application of pairs and the pigeonhole principle, ultimately proving the claim.

Think of a classroom where each student can only reach the top shelf if there are only 5 shelves. If you assume every student can only reach up to the 5th shelf, but you have 6 students trying to reach, you will find at least one pair who can reach the same height, leading to contradictory outcomes. This illustrates how our assumption that all subsequences are limited in length must be incorrect.

--