Let a1; a2; a3; : : : ; a1001 be a sequence of integers. Prove that it must contain a

Chapter 25, Problem 25.13

(choose chapter or problem)

Let a1; \(a_{1}, a_{2}, a_{3}, \ldots, a_{1001}\) be a sequence of integers. Prove that it must contain a subsequence of length 11 that is

(a) increasing,

(b) decreasing, or

(c) constant. In other words, we can find indices \(i_{1}<i_{2}<\cdots<i_{11}\) such that one of the following is true:

\(\begin{array}{l}
a_{i_{1}}<a_{i_{2}}<a_{i_{3}}<\cdots<a_{i_{11}} \\
a_{i_{1}}>a_{i_{2}}>a_{i_{3}}>\cdots>a_{i_{11}} \\
a_{i_{1}}=a_{i_{2}}=a_{i_{3}}=\cdots=a_{i_{11}}
\end{array}\)

Next, create a sequence of only 1000 integers that does not contain a subsequence that is increasing, decreasing, or constant.