C1. Sara has 10 blocks numbered $1 \mathrm{t} / \mathrm{m}$ 10. She wants to stack all the blocks into a tower. A block can only be placed on top of a block with a higher number, or on a block with a number that is exactly one lower. An example is, from top to bottom: 2, 1, 5, 4, 3, 6, 7, 9, 8, 10. How many different towers are possible?
C1. Let's first examine the problem for a smaller number of blocks with consecutive numbers. With 1 block, there is only 1 possible tower. With 2 blocks, both the 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. With 4 blocks, these are the possible towers:

$$
\begin{array}{llll}
1-2-3-4, & 1-2-4-3, & 2-1-3-4, & 2-1-4-3, \\
1-3-2-4, & 1-4-3-2, & 3-2-1-4, & 4-3-2-1 .
\end{array}
$$

It seems that the number of towers doubles each time. We will prove this. Given a tower of $n>1$ blocks, consider the block with the highest number, $n$. If this block is on top of another block, it must be a block with a lower number (since there is no block with a higher number), so according to the condition, it must be on top of the block with number $n-1$. Therefore, block $n$ is either at the bottom or directly on top of block $n-1$. Since all other blocks can also be on top of block $n-1$, we see that if we remove block $n$, a valid tower with $n-1$ blocks remains.

Now we want to show that we can also create a tower with $n$ blocks from any (valid) tower with $n-1$ blocks. In any (valid) tower with $n-1$ blocks, we can insert block $n$ either at the bottom or on top of block $n-1$; other positions are not possible, and in this way, block $n$ will never be on a block with a too small number. In both cases, the tower of $n$ blocks becomes a valid tower, because any other block can be on top of block $n$. From any (valid) tower with $n-1$ blocks, two valid towers with $n$ blocks can thus be created.

We see that the number of towers indeed doubles each 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. The number of towers with 10 blocks is thus $2^{9}=512$.