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 where . We will start from . Now, select the next number which is less than . This way we can form a subsequence

. If we are done. If not, we will remove this subsequence from the original one. Also, note that for every element in the remaining sequence there exist an element such that . Repeat the same procedure again on the remaining sequence, we will have

and so on. If at any time we are done. If not, we can have at least r+1 different subsequences. For an element there exist an element . This way, we have an increasing subsequence

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

–Saurabh Joshi

### Like this:

Like Loading...

*Related*

Tags: math, theorem

This entry was posted on May 30, 2008 at 9:41 am and is filed under math, theorem. You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.

## Leave a Reply