# In a sequence of distinct numbers of length $n$ there is a monotonic subsequence of length at least $\lceil \sqrt{n} \rceil$

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.

• Why "random"? Do you just mean any given sequence of $n$ numbers? – MPW Feb 8 '14 at 15:53
• Yes. Sorry for the confusion. – Arek Krawczyk Feb 8 '14 at 15:55
• 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)? – MPW Feb 8 '14 at 15:55
• Sorry again, added the requirement for the numbers to be distinct. – Arek Krawczyk Feb 8 '14 at 15:56
• 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. – MPW Feb 8 '14 at 15:56