18.4.2. Applying Restrictions and Solving

A subsequence means here that the values may not be consecutive. That means I am allowed to miss a few numbers. In the sense, say I take a sequence 1, 3, 0, -5, 2, 8 and so on. Then I can choose to pick 1 and then exclude 3 and 0 and -5. This is a subsequence. In the same way I can pick a subsequence saying 3, 2 and 8 that means I skip 0, I skip -5.

A subsequence is a series of selected elements from a sequence where the order is preserved, but not necessarily consecutive. For example, if we have a sequence like 1, 3, 0, -5, 2, 8, we can create subsequences such as 1, -5, and 2 (by selecting specific numbers) or even 3, 2, and 8 (skipping some numbers in between). The important point is that any selection maintains the original order from the parent sequence.

Imagine you're collecting stickers from a variety of sets. If you have a complete album (the full sequence) but only want to showcase a few highlights at a party, you can choose certain stickers (the subsequence) to display without going in order. Perhaps you choose the first sticker, skip a few, and then grab one from later in the album. Your selection is not consecutive but still reflects what you want to showcase from your collection.

So what this question basically says is that irrespective of the way your $n+1$ distinct real numbers are chosen you always have a subsequence. 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. But the number of values are $n+1$ such that if you view those $n+1$ values they are either strictly increasing or strictly decreasing.

The claim here is that no matter how you select $n+1$ distinct real numbers, there will always be some subsequence of these numbers that is either strictly increasing or strictly decreasing. To clarify, strictly increasing means each next number in the subsequence is larger than the previous one (e.g., 1, 2, 3), while strictly decreasing means each next number is smaller (e.g., 3, 2, 1). This property holds true across various sequences and guarantees the presence of such subsequences.

Think of a race involving runners of varying speeds. Regardless of how they finish (their times can be mixed: some fast, some slow), if you take the finishing order (the sequence), you’ll inevitably find at least one group of runners who finished in increasing speed (the fastest runners) or one that finished in decreasing speed (the slowest). This highlights that regardless of the arrangement, groups with uniform trends are guaranteed.

So by PHP here I mean pigeonhole principle. So pigeonhole principle guarantees me that you definitely have a pair of values here say $a_i$ and $a_j$ such that your $l_i$ and $l_j$ are the same.

The Pigeonhole Principle states that if you have more items than containers to put them in, at least one container must hold more than one item. In this context, if you take the lengths of increasing and decreasing subsequences of your distinct numbers, and since there are only $n$ possible lengths, but you have more sequences, at least one length must repeat. This is crucial for proving that there must be subsequences as described.

Imagine you have ten pairs of shoes but only six shelves to store them. According to the pigeonhole principle, at least one shelf must contain more than one pair of shoes because there are more pairs (pigeons) than places to put them (holes). Similarly, this principle in the sequence of numbers ensures there are repeated lengths of subsequences leading to our conclusions.

I assume that the statement is false and that means for each $a_i$ in the sequence, the value $l_i$ is at most $n$.

To prove something by contradiction, you assume the opposite of what you want to prove and show that leads to an impossibility. Here, if it were true that every subsequence's lengths are at most $n$, then when paired with their maximums, you would not have enough unique lengths for each item in your list, leading to a contradiction. It shows the flaw in the original assumption, thus validating the existence of either increasing or decreasing subsequences of the required length.

Consider a classroom of students where each student can only stand on their assigned spot and there are only ten spots for them. If you argue that every student occupies a unique spot without overlaps, but you have twelve students, you reach an impossibility as some students need to share spots. This logic illustrates the contradiction that arises when assuming all sequences meet a condition that they can't possibly meet.

--