While doing Pigeonhole principle in our class, our professor mentioned and proved that every permutation of $n$ either has a decreasing or an increasing subsequence of length ⌈$\sqrt n$⌉.
But how do I prove that the above theorem is the strongest possible ?
Here is a proof that $\lceil \sqrt n\rceil$ is the best result possible, for all $n$.
Given $n$, let $s=\lceil \sqrt n\rceil$. Note that $s^2$ is the smallest perfect square which is greater than or equal to $n$. Every integer in the range $\{0,1,\dots,s^2-1\}$ can be uniquely written in the form $$ i\cdot s+j,\qquad i,j\in \{0,1,\dots,s-1\} $$ First, we will define a permutation $\pi$ of length $s^2$ without any monotone sequences of length $s+1$. Then, we will modify $\pi$ so it has length $n$, but still without any monotone sequences of length $s+1$.
$$ \begin{align} \pi:\{0,1,\dots,s^2-1\}&\to \{0,1,\dots,s^2-1\}\\ i\cdot s+j&\mapsto j\cdot s + (s-1-i) \end{align} $$ When $s=4$, this looks like $$ \pi=\left(\begin{matrix}0&1&2&3&4&5&6&7&8&9&10&11&12&13&14&15\\ 3&7&11&15&2&6&10&14&1&5&9&13&0&4&8&12\end{matrix}\right) $$ This takes care of the cases when $n=s^2$ is a perfect square. Otherwise, we need to shorten $\pi$. We do this by only keeping the first $n$ entries of $\pi$. Then, we reduce these entries so that they are in the range $\{0,1,\dots,n-1\}$ without changing their relative ordering.
For example, suppose $n=11$. We find $s=4$, so we start with the above $\pi$. We then only keep the first $11$ entries, resulting in $$ \left(\begin{matrix} 0&1&2&3&4&5&6&7&8&9&10\\ 3&7&11&15&2&6&10&14&1&5&9 \end{matrix}\right) $$ The domain is now $\{0,1,\dots,10\}$, which is correct, but the range is all wrong. To fix this, replace the smallest number in the range with $0$, the second smallest number in the range with $1$, and so on. The resulting permutation of length $11$ with no monotone subsequences of length $5$ is $$ \left(\begin{matrix} 0&1&2&3&4&5&6&7&8&9&10\\ 2&5&8&10&1&4&7&9&0&3&6 \end{matrix}\right) $$