The classical Erdős-Szekeres theorem says that any sequence of $n^2+1$ real numbers contains a monotonic $(n+1)$-term subsequence. Suppose, however, that we want to find a subsequence which is not necessarily monotonic itself, but has the sequence of its first differences monotonic. How long has the original sequence to be to ensure that such an $(n+1)$-term subsequence can be found?
For positive integer $n$, what is the smallest integer $N=N(n)$ such that every $N$-element sequence of real numbers contains an $n$-element subsequence $(a_1,\ldots,a_n)$ with either $a_2-a_1\le\dotsb\le a_n-a_{n-1}$, or $a_2-a_1\ge\dotsb\ge a_n-a_{n-1}$?
Trivially, we have $N(1)=1$, $N(2)=2$, and $N(3)=3$. However, I do not know the value of $N(4)$.
The state of the art as of 05.03.12. The nice argument of Boris Bukh (below) shows that $N(n)$ is exponential in $n$. Still, this does not completely settle the problem.
Updated 16.03.12: the absolutely beautiful, must-upvote solution by Sergey Norin is posted below.
