Permutation of 1…9 with no ascending or descending subsequence of length 4 Arrange the numbers $1,2,...,9$ in such an order that no four of them appear (adjacently or otherwise) in ascending or descending order. 
Show that there is no arrangement of the numbers $1,2,...,10$ with this property.
Now suppose $n>1$, and find the maximum $k$ such that the numbers $1,2,...,k$ can be arranged with no $n$ of them in ascending or descending order.
 A: $k = (n - 1)^2$
You need to arrange the $k$ numbers in $n - 1$ groups of $n - 1$ descending elements, where every following group is bigger than the previous.
In the case of $n = 4$ we have
$3\:2\:1\hspace{8 pt}6\:5\:4\hspace{8 pt}9\:8\:7$ or $3$ groups of $3$. Introducing a $10$th element will break the ascending/descending limit of a subsequence, regardless of where it is placed.
Following this logic, we can show that for any $n$ if we take the first $(n - 1)^2$ numbers and arrange them as follows
$\underbrace{\underbrace{n - 1\:\dots\:1}_{n - 1}\hspace{8 pt}\underbrace{2(n - 1)\:\dots\:n}_{n - 1}\:\dots\:\underbrace{(n - 1)(n - 1)\:\dots\:((n - 2)(n - 1) + 1)}_{n - 1}}_{n - 1}$
the maximum length of an ascending/descending subsequence is $n - 1$ (e.g. $n - 1 - 1 + 1 = n - 1$ from the first group) and there is no ascending/descending subsequence of length $n$. 
Now if you add a new element, namely the $((n - 1)^2 + 1)$th one, we introduce an ascending/descending subsequence of length $n$ using the logic above. Hence, the maximum for $k$ is $(n - 1)^2$.
A: For the first question consider this sequence $5\ 3\ 7\ 1\ 9\ 4\ 2\ 8\ 6$. None $4$ of them are increasing or decreasing.
