Hammersley gave the following algorithm that proves the theorem.
Let a sequence $a_1,a_2,...,a_{n^2+1}$.
(a) let $a_1$ start the first column and for $i\ge 1$
(b) if $a_i$ is greater than or equal to the value that is on top of a column, we put $a_i$ on top of the column on top of the first such column, and
(c) otherwise start a new column with $a_i$.
Since $n^2+1$ numbers are placed into the column structure, one must have either a column which its height is greater than $n$ or more than $n$. So, we get a monotone subsequence of length $n+1$.
I would like to create a matrix that visualizes the above algorithm.
So far I have got a sequence of $n^2$ numbers:
$$n,n-1,\ldots,1,2n,2n-1,\ldots,n+1,3n,3n-1,\ldots,2n+1,\ldots,n^2,n^2-1,\ldots,(n-1)n+1$$
I know how to construct a matrix with entries the above numbers (see here for the matrix). But I don't know how to extend the sequence to $n^2+1$ numbers and construct a matrix without repeating the numbers.
I would really appreciate any help.
Thank you.
The point of Hammersley’s argument is that if you extend the sequence by one term, say $x$, then either $x\ge (n-1)n+1$, in which case it will go at the top of one of the existing columns, or $x<(n-1)n+1$, in which case it will start a new column. In the first case you will have a column of height $n+1$ whose elements form an increasing subsequence of the original sequence. In the second case
$$n^2,n^2-1,n^2-2,\ldots,(n-1)n+1,x$$
is a decreasing subsequence of the original sequence of length $n+1$. Thus, in either case you find that the extended sequence of length $n^2+1$ has a monotone subsequence of length $n+1$.