GO AWAY! You're not allowed to read this writeup before reading about the monotone sequence theorem! However, TheBooBooKitty asked me to point out that pirated proofs are more valuable than the ones that come in boxes like this one. So for maximal value, don't read this node at all; try to prove the theorem on your own.

Still here? OK, so say we have a *finite sequence* a_{1},...,a_{mn+1} with neither an ascending subsequence of length m+1 nor a descending subsequence of length n+1.

Let b_{i} be the length of the longest ascending subsequence which begins at a_{i}, and let c_{i} be the length of the longest descending subsequence which begins there. Obviously, (a_{i}) is always both an ascending and a descending subsequence, so 1≤b_{i},c_{i}. And our assumption in that b_{i}≤m and c_{i}≤n. So there are m*n different possible pairs of values for (b_{i},c_{i}). But there are m*n**+1** of these values...

By Dirichelet's Pigeonhole Principle (or by plain common sense), this means that for some pair i<j we have b_{i}=b_{j} and c_{i}=c_{j}. 'Cause no matter how good a mathematician you are, you cannot pick mn+1 *different* values out of a set of just mn values.

Surprisingly, we're done! For suppose a_{i}≤a_{j}. Then the subsequence beginning with a_{i} and continuing with the ascending subsequence of a_{j} is ascending and has length 1+b_{j}=1+b_{i}, in contradiction to the definition of b_{i}. And if a_{i}≥a_{j}, then the subsequence beginning with a_{i} and continuing with the *descending* subsequence of a_{j} is descending and has length 1+c_{j}=1+c_{i}, in contradiction to the definition of c_{i}.

Either way, we get a contradiction. So our original assumption — that ∀i.b_{i}≤m&c_{i}≤n — is flawed; there exists either a weakly ascending subsequence of length m+1 or a weakly descending subsequence of length n+1.