Theorem: Every sequence of $n^2 + 1$ distinct real numbers contains a subsequence of length $n + 1$ that is either strictly increasing or strictly decreasing.
So for $n = 3$ here is a sequence of $3 \times 3 + 1 = 10$ distinct integer numbers(since integers are real as well).
1 10 2 9 3 8 4 7 5 6
According to theorem there must be a sequence of $3 + 1 = 4$ length that is either strictly increasing or strictly decreasing. I now list all the $4$ length
sub-sequences.
1 10 2 9
10 2 9 3
2 9 3 8
9 3 8 4
3 8 4 7
8 4 7 5
4 7 5 6
I am unable to find any of them to be strictly increasing or strictly decreasing.
Does it means that theorem is false?
Best Answer
There are many more subsequences of length $4$ than just those you have listed. All of yours consist of consecutive elements of the original sequence, but it is also allowed for a subsequence to skip elements.