I am reading the book "Ramsey theory on the integers" by Bruce M.Landman and Aaron Robertson. There they proved that within any sequence of $n^2+1$ numbers there exists a monotonic subsequence of length $n+1$ by using Pigeonhole principle.
But I am trying to prove the following: given a sequence of only $n^2$ numbers, there need not be a monotonic subsequence of length $n+1$.
I find the following sequence for $n=2$: $1, 0, 6, -1$ But I can't find even for $n=3$ and not able to generalize for arbitrary $n$
Could any help please?
$3,6,9,2,5,8,1,4,7$ right? This should work. Generalisation should be straightforward, and if it isn't I'd be happy to explain. Just comment. Okay, for general $n$ take
$n,2n,3n,4n,\cdots,n^2,n-1,2n-1,3n-1,n^2-1,n-2,\cdots,\cdots,1,n+1,2n+1,3n+1,\cdots,n^2-n+1$
EDIT: Take $n$ APs, each of length $n$ with common difference $n$. The first starts at $n$, the second at $n-1$, the third at $n-2$ etc all the way down to 1. Then we concatenate them.