Increasing or decreasing subsequence

Well,

I found this problem here. Solution to the second puzzle given in that post is already posted in Kissa Kursi Ka. I tried a couple of approaches to solve the first one but could not succeed. Finally, Deepanjan came up with a very elegant solution, so the entire credit goes to him for providing the solution to the first problem.

Just now I saw a message from Saket that this problem is known as Erdős–Szekeres theorem. No wonder that Erdös was part of this fascinating problem.

For those who are wondering what I am talking about, I am copying the problem in question over here.

Problem : Given a sequence of r*s+1 distinct integers (r>=1, s>=1) prove that there exists either an increasing subsequence of length r+1 or a decreasing subsequence of length s+1 ( taken from viked’s blog )

Solution : The first observation is that r and s are interchangeable. Nevertheless, we will start proving that either we have a decreasing subsequence of length s+1 or an increasing subsequence of length r+1.

Let the sequence of distinct integers be $a_1, a_2, \dots, a_m$ where $m = r*s +1$. We will start from $a_1 = a^1 _1$. Now, select the next number $a_i = a^1 _2$ which is less than $a_1$. This way we can form a subsequence

$a^1 _1, a^1 _2, \dots a^1 _{k_1}$. If $k_1 \geq s+1$ we are done. If not, we will remove this subsequence from the original one. Also, note that for every element $a_j$ in the remaining sequence there exist an element $a^1 _i$ such that $a^1 _i < a_j$. Repeat the same procedure again on the remaining sequence, we will have

$a^2 _1, a^2 _2, \dots , a^2 _{k_2}$ and so on. If at any time $k_i \geq s+1$ we are done. If not, we can have at least r+1 different subsequences. For an element $a^n _j$ there exist an element $a^{n-1} _i < a^n _j$. This way, we have an increasing subsequence $a^1 _{i_1} < a^2 _{i_2} < \dots < a^{r+1} _{i_{r+1}}$

This proof by Deepanjan is so elegant that I would indeed call it a beautiful proof.

–Saurabh Joshi