Strictly Increasing/Decreasing Subsequences
|
|
Subsequences
|
|
If a1, a2, a3, ..., aN is a sequence of real numbers, then a subsequence would be a new sequence of numbers that include some, but not necessarily all of the numbers of the original sequence, and in the same order as they appeared in the original sequence.
For example, a possible subsequence of the sequence 1, 2, 3, 4, 5, 6, 7 could be 2, 4, 6, 7. Another possible subsequence could be 1, 2, 3. There are many more possible subsequences.
Any sequence of numbers can be what is called "strictly increasing" whenever each term in the sequence is smaller than the term that comes after it. A sequence is called "strictly decreasing" whenever each term in the sequence is larger than the term that comes next.
|
Theorem of Strictly Increasing/Decreasing Subsequences
|
|
The Theorem of Strictly Increasing/Decreasing Subsequences states that every sequence of n2 + 1 distinct real numbers contains a subsequence of length n + 1 that is either strictly increasing or stictly decreasing. |
|
|
Example 1: |
If there was a set with 65 elements in it, determine the maximum length in which there must be a strictly increasing or strictly decreasing subsequence. Hint: use the Theorem of Strictly Increasing/Decreasing Subsequences. |
|
Solution
|
|
Example 2: |
Given the set {7, 13, 9, 4, 22, 3, 1, 19, 14, 10, 12, 37, 6, 2, 15, 18, 25} figure out if there must be a strictly decreasing subsequence of length 5, using the Theorem of Strictly Increasing/Decreasing Subsequences. |
|
Solution
|
|
Example 3: |
Find a subsequence from the set in Example 2
that is strictly increasing, and one that is strictly decreasing,
each of length 5, if they exist. |
|
Solution
|
|
|