
Combinatorics proof help
Prove that in any sequence $\displaystyle a_1, a_2,...,a_{mn+1}$ of $\displaystyle mn+1$ distinct real numbers, there are either $\displaystyle m+1$ numbers (not necessarily consecutive) that occur in increasing order, or $\displaystyle n+1$ that occur in decreasing order.
HINT: For each term $\displaystyle a_i$, consider the ordered pair $\displaystyle (x_i, y_i)$, where $\displaystyle x_i$ and $\displaystyle y_i$ are the lengths of the longest increasing and decreasing subsequences ending with $\displaystyle a_i$. The conclusion holds if there is an $\displaystyle i$ for which $\displaystyle x_i \geq m+1$ or $\displaystyle y_i\geq n+1$.
I've seen a proof for this which involves $\displaystyle x_i$ and $\displaystyle y_i$ where one is a subsequence ending in $\displaystyle a_i$ and the other begins with $\displaystyle a_i$ but this hint is different. Can someone help me get started?