I need to prove that in any sequence of distinct numbers of length $n$ there is a monotonic subsequence of length at least $\lceil \sqrt{n} \rceil$.

I thought, that induction would probably be best here.

So $n=1$ and $n=2$ are trivial.

Now let's assume all is well for $k \leq n$ and consider $n+1$. If from the first $n$ elements we can create a decreasing/increasing sequence and the last elements is smaller/bigger than all of them then this is trivial. We can also do the same analysis with the first element.

But what about other cases? I have literally now idea how to approach them.

  • $\begingroup$ Why "random"? Do you just mean any given sequence of $n$ numbers? $\endgroup$ – MPW Feb 8 '14 at 15:53
  • $\begingroup$ Yes. Sorry for the confusion. $\endgroup$ – Arek Krawczyk Feb 8 '14 at 15:55
  • $\begingroup$ What if the numbers just happen to be (1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2)? $\endgroup$ – MPW Feb 8 '14 at 15:55
  • $\begingroup$ Sorry again, added the requirement for the numbers to be distinct. $\endgroup$ – Arek Krawczyk Feb 8 '14 at 15:56
  • $\begingroup$ Oh, I guess you don't mean in the order given. So you could rearrange my numbers as 1,1,1,1,1,1,1,...,2,2,2,2,2,2,2 . I see. $\endgroup$ – MPW Feb 8 '14 at 15:56

This is the theorem of Erdos and Szekeres. There are about a half dozen proofs in the paper http://stat.wharton.upenn.edu/~steele/Papers/PDF/VOTMSTOEAS.pdf


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.