Combinatorics: Prove that for a sequence with $mn+1$ one of these statements is correct

Question

Assume $m$ and $n$ are to natural numbers. Prove that in a sequence of $mn+1$ numbers, there is an ascending sequence with length of $n+1$ or a descending sequence with length of $m+1$

How do you prove this statement?

Answer 1

Let $\{a_i\}$ be a sequence of $mn+1$ terms.

If there is an increasing sequence of length $n+1$, then the conclusion holds. Therefore, lets assume there is not an increasing sequence of length $n+1$.

Let $l(i)$ denote the length of the longest increasing subsequence ending at $a_i$. Since there is no increasing sequence of length $n+1$, we see that for each term index $i$, $l(i)$ is an integer such that $1 \leq l(i) \leq n$.

Since there are $mn+1$ terms in the sequence, there are $mn+1$ values $l(i)$ to consider. Each $l(i)$ can be one of $n$ values. By the Pigeonhole Principle, there are $m+1$ indices that have the same value for $l(i)$.

We order the indices as follows: $$ i_1 < i_2 <i_3 < \cdots < i_m < i_{m+1} $$ and we have that $$ l(i_1)= l(i_2)=l(i_3)= \cdots=l(i_m) =l(i_{m+1}) = L$$ The claim is that the terms selected by these indices form a decreasing sequence, that is: $$ a_{i_1} > a_{i_2} > a_{i_3} > \cdots > a_{i_m} > a_{i_{m+1}} $$ We show this by contradiction. Assume there are two indices $i_{k_1}$ and $i_{k_2}$ such that: $$ i_{k_1} < i_{k_2} \quad \wedge \quad a_{i_{k_1}} \leq a_{i_{k_2}}$$ Then we see that, since $l(i_{k_1})=L$, we could take the term $a_{i_{k_2}}$ and create an increasing subsequence of length $L+1$ ending at this term, meaning $l(i_{k_2}) \geq L+1$. This contradicts that it must equal $L$. Therefore, the terms form a decreasing sequence: $$ a_{i_1} > a_{i_2} > a_{i_3} > \cdots > a_{i_m} > a_{i_{m+1}} $$

Answer 2

That is usually mentioned as the Erdos-Szekeres', or Dilworth's, theorem. Let us assume that $h_1,\ldots,h_{mn+1}$ is our sequence, with $h_a$ representing the height of the $a$-th person. Let us assume that these people have to go to a post office with $m$ queues. The first person arrives and takes place in the first empty queue. The second person arrives and if $h_2>h_1$ he/she takes place behind the first person, otherwise takes place in the first free queue. The process continues till placing $h_{mn}$. When $h_{mn+1}$ arrives, only two mutually exclusive things might happen:

1. $h_{mn+1}$ is able to take place in some queue. In such a case there are $mn+1$ people in $m$ queues, hence some queue is made by at least $n+1$ people, and it gives an increasing subsequence;
2. $h_{mn+1}$ is not able to take place in any queue. Then the last person in every queue and $h_{mn+1}$ form a decreasing subsequence of $m+1$ terms.

This theorem can be used to give an unconventional proof of the Bolzano-Weierstrass theorem, for instance. Historically, it gave a fundamental Lemma for tackling the happy ending problem.