Dutch Mathematical Olympiad

We will first look at the problem for a smaller number of blocks. With $1$ block, only $1$ tower is possible. With $2$ blocks, both towers (top) $1$-$2$ (bottom) and $2$-$1$ are possible. With $3$ blocks, these are the possible towers: $1$-$2$-$3$, $2$-$1$-$3$, $1$-$3$-$2$, and $3$-$2$-$1$. It seems that the number of towers doubles each time. We are going to prove this. Starting from a tower with $n>1$ blocks, consider the block with the highest number, $n$. If this block lies on top of another block, then this must be a block with a lower number (as there does not exist a block with a higher number), and according to the requirements it has to lie on the block with number $n-1$. Hence, block $n$ lies either completely on the bottom, or directly on top of block $n-1$. Because all other blocks can also lie on top of block $n-1$, we see that after removing block $n$, we are left with a valid tower of $n-1$ blocks.

Now we want to show that from any (valid) tower of $n-1$ blocks we can make a valid tower of $n$ blocks. In every (valid) tower of $n-1$ blocks we can insert block $n$ either at the bottom or directly on top of block $n-1$; other places are not allowed and in this way block $n$ never lies on a block with a number that is too small. In both cases the tower of $n$ blocks is a valid one, because on top of block $n$ any other block is allowed. So from any valid tower of $n-1$ blocks we can make two valid towers of $n$ blocks.

So we see that the number of towers indeed doubles every time. For $n=1$ there is $1=2^0$ tower, for $n=2$ there are $2=2^1$ towers and in general there are $2^{n-1}$ towers. So the number of towers with $10$ blocks is $2^9=512$.