Problem 1022

Proof: Let the given sequence be $a_{1}, a_{2}, \cdots, a_{m n+1}$, denoted by $\pi$. Suppose the sequence $\pi$ does not have an increasing subsequence of length $m+1$. Let $\pi_{k}(k=1,2, \cdots, m n+1)$ represent the longest increasing subsequence of $\pi$ starting with $a_{k}$. Then the length of $\pi_{k}$ is no more than $m$. Let $A=\left\{\pi_{1}, \pi_{2}, \cdots, \pi_{m n+1}\right\}$, then $|A|=m n+1$. Let $A_{i}$ $(i=1,2, \cdots, m)$ represent the set of sequences in $A$ with length $i$, then $\bigcup_{i=1}^{m} A_{i}=A$. By the general form of the pigeonhole principle, there must be an integer $k(1 \leqslant k \leqslant m)$ such that $\left|A_{k}\right| \geqslant n+1$. Suppose $\pi_{k_{1}}, \pi_{k_{2}}, \cdots, \pi_{k_{n+1}}\left(k_{1}<k_{2}<\cdots<k_{n+1}\right)$ are any $n+1$ elements in $A_{k}$, then it must be that $a_{k_{1}} \geqslant a_{k_{2}} \geqslant \cdots \geqslant a_{k_{n+1}}$, otherwise there exists a positive integer $s(1 \leqslant s \leqslant n)$ such that $a_{k_{s}}<a_{k_{s+1}}$. By placing $a_{k_{s}}$ at the beginning of the sequence $\pi_{k_{s+1}}$, we obtain an increasing subsequence of $\pi$ starting with $a_{k_{s}}$ with length $k+1$. However, $\pi_{k}$ is the longest increasing subsequence of $\pi$ starting with $a_{k}$, with length $k$, leading to a contradiction. Therefore, $a_{k_{1}}, a_{k_{2}}, \cdots, a_{k_{n+1}}$ is a decreasing subsequence of $\pi$ with length $n+1$. Hence, if the sequence $\pi$ does not have an increasing subsequence of length $m+1$, it must have a decreasing subsequence of length $n+1$.