18.3. Divisibility in Arbitrary Subsets

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.

In this section, we are discussing a key property of sequences. Given any list of $n + 1$ distinct real numbers (which can be in any order), it is possible to always find a smaller ordered list (subsequence) where the numbers continuously rise (increasing) or fall (decreasing). This means that regardless of how the numbers are arranged initially, we can find at least one pattern of order among them.

Think of a group of students who are all of different heights standing in a random order. You can always find at least one smaller group of students standing in a line such that each student in line is taller than the one before them (increasing), or shorter (decreasing).

First of all, what is a strictly increasing sequence? A sequence of the form $(a_1, a_2, ...)$ where $a_1 < a_2 < a_3 < ...$. Whereas if I have a sequence of the form $(a_1, a_2, a_3, ...)$ where $a_1 > a_2 > a_3 > ...$, then it is a strictly decreasing sequence.

A strictly increasing sequence is when each number is larger than the previous number. For example, in the sequence $(2, 4, 6, 8)$, each number is greater than all the ones before it. Conversely, a strictly decreasing sequence contains numbers where each is less than the one before it, like in $(10, 8, 6, 4)$. Understanding these definitions is crucial because they help us identify the patterns we are trying to find in any set of distinct real numbers.

Consider a race: if you wanted to determine if any runner consistently gained speed compared to the others, you would look for a strictly increasing sequence of their speeds at each marker. On the other hand, if a runner started fast but slowed down consistently, that would represent a strictly decreasing sequence of speeds.

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

A subsequence is a series of numbers selected from a sequence without changing their relative order. This means you can skip some numbers to form a new sequence while still retaining the original order of those chosen numbers. For instance, from the sequence $(1, 3, 0, -5, 2, 8)$, a valid subsequence could be $(1, 2, 8)$ or $(3, 2, 8)$, where the numbers do not have to be next to each other in the original sequence.

Think of selecting winners from a list of participating students in a talent show. The students performed on different days, and you don't have to select everyone who performed—you can pick few winners based on their performances - not in the order they performed.

Why I am taking arbitrary here? Because I want to prove this statement for every sequence. This is a universally quantified statement, and to prove a universally quantified statement, I can use the universal generalization principle by proving that a statement is true for some arbitrary element of the domain.

To validate the claim regarding subsequences, we assume that our selected sequence of $n + 1$ distinct real numbers is arbitrary. By using the universal generalization principle, we demonstrate that our statement holds true regardless of the specific numbers chosen, thus affirming its universal applicability. This approach helps in establishing mathematical truths based on general cases, leading to broader conclusions.

Imagine a bakery that wants to ensure that all types of bread turn out delicious, regardless of the ingredients used. By testing one batch of each type and ensuring they all meet a standard, the bakery can confidently assert that all bread varieties will be tasty.

So let me first define two values. I define $L_i$ as the length of the longest increasing subsequence starting at $a_i$. One might be of length 1; a trivial increasing subsequence starting at $a_i$ is the value $a_i$ itself.

To help analyze the properties of increasing sequences, we denote the length of the longest increasing subsequence beginning at each number in our sequence. This helps in systematically determining how many increasing subsequences exist starting from any given number, thus laying the groundwork for identifying pairs of numbers that follow the subsequence condition within the entire set.

Think of a race where each runner can have their individual performance milestones tracked. Each runner (i.e., each number in the sequence) has a highest performance they achieved since the start of the race—this represents their 'longest increasing subsequence' starting from their current state.

But how many numbers do I have in the sequence? I have $n + 1$ values in the sequence that I have chosen. That means I have more pigeons and less holes.

In employing the pigeonhole principle, we observe that we have $n + 1$ distinct entries for our subsequences. When we attempt to categorize this into increasing and decreasing subsequences, we will encounter a situation where the number of pairs (our 'pigeons') exceeds the available slots or categories (our 'holes') for those pairings. This oversaturation guarantees that at least one number must share a similar attribute—either its increasing or decreasing sequence with another number.

Imagine trying to fit 10 different colored candies into only 9 bags. Since there are more candies than bags, at least one bag must contains more than one candy. Similarly, in our sequence, at least one pair must exhibit the same subsequence behavior, either going up or down.

--