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

Advertisements

Tags: ,

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: