$a)$ Find a sequence of four distinct real numbers with no decreasing or increasing subsequence of length $3.$
$b)$ Find a sequence of nine distinct real numbers with no decreasing or increasing subsequence of length $4.$
$c)$ Generalize the result in parts $(a)$ and $(b).$
Some how I manage two sequence $2,4,1,3$ and $3,6,9,2,5,8,1,4,7$ respectively for $(a)$ and $(b)$. How to Generalize that$?$ I got the solution
For $n\geq 2,$ there exists a sequence of $n^2$ distinct real numbers with no decreasing or increasing subsequence of length $n+1.$ Consider $$n,2n,3n,\cdots ,(n-1)n,n^2,(n-1),(2n-1),\cdots,(n^2-1),(n-2),(2n-2),\cdots,(n^2-1),(n-2),(2n-2),\cdots,(n^2-2),\cdots,1,(n+1),(2n+1),\cdots,(n-1)n+1.$$
But I didn't get how they manage to find that sequence$?$ Any help will be appreciated.
Thanks in advanced.
Best Answer
Maybe an easier way is to make an $n \times n$ grid, fill it in with numbers from $1$ to $n^2$ in lexicographic order, then read the rows from the bottom up. So it would be $3,4,1,2$ and $7,8,9,4,5,6,1,2,3$.
There is obviously no increasing sequence with more than $n$ terms since the numbers just go up in $n$ unit blocks before decreasing forever. And a decreasing subsequence could only use at most one number from each of those blocks, so it couldn't be longer than $n$ terms either.
Your method works too, but it's slightly harder to show that the increasing subsequences can't be too long. It's obvious if you write out the grid and track what an increasing sequence would have to look like.
Here is your sequence written in lexicographic form. Notice that to make a subsequence that is increasing you can only choose terms that are to the right or below the previous term, so you cannot have more terms than columns in an increasing subsequence.