In how many ways can the numbers $1,2, \ldots, n$ be arranged in a sequence such that, except for the number in the first position, each number is preceded by at least one of its (original order) neighbors?
I. solution. Consider a suitable arrangement, and look at the largest element, $n$. No matter where it stands in the sequence, its only neighbor, $(n-1)$, must precede it. $(n-1)$, in turn, must be preceded by $(n-2)$, since its other neighbor, $n$, is behind it. This continues until we reach the first element of the arrangement. If this is $k$, then in the arrangement the numbers $k, k+1, \ldots, n-1, n$ appear in this order.

Now consider the smallest element, 1. No matter where it is - except if it is in the first position, i.e., $k=1$ - it must be preceded by its only neighbor, 2. This, in turn, must be preceded by 3, since its other neighbor, 1, is behind it. This continues up to $(k-1)$, which is preceded by its neighbor, $k$, since $k$ is in the first position. Thus, in the arrangement starting with $k$, the order of the numbers smaller than $k$ is also unique: $k-1, k-2, \ldots, 2, 1$.

If we fix the first element, $k$, then the numbers $k-1, k-2, \ldots, 2, 1$ can be written in this order in $\binom{n-1}{k-1}$ ways on the $n-1$ free positions, and then the placement of the numbers larger than $k$ on the remaining positions is unique due to the fixed order.

The number of possible arrangements is thus

$$
\sum_{k=1}^{n}\binom{n-1}{k-1}=2^{n-1}
$$

Csirmaz Előd (Fazekas M. Főv. Gyak. Gimn., 10th grade)

II. solution. First, we prove that in a suitable arrangement, the last position is occupied by either 1 or $n$. Suppose this is not true, let $1<i<n$, and suppose the last element of the sequence is $i$. Then both neighbors of $i$, $i+1$ and $i-1$, must precede it. Then the numbers larger than $i$ precede the smaller one, and the numbers smaller than $i$ precede the larger one, so their other neighbor must precede them.

This results in two chains:

$$
n \leftarrow \ldots \leftarrow i+2 \leftarrow i+1
$$

$$
i \leftarrow \ldots \leftarrow i-2 \leftarrow i-1
$$

This implies that both 1 and $n$ must be in the first position, which is clearly impossible. Therefore, either 1 or $n$ must be in the last position. Whether 1 or $n$ is in the last position, any of the $f(n-1)$ possible arrangements of the remaining numbers gives a valid $n$-length sequence, so $f(n)=2 f(n-1)$. Since $f(1)=1$, we have $f(n)=2^{n-1}$.

Vizer Máté (Fazekas M. Főv. Gyak. Gimn., 11th grade)

III. solution. Let $1 \leq k \leq n$, and place $k$ in the first position. The second element is then a neighbor of $k$, either $k-1$ or $k+1$. (If $k=1$ or $k=n$, then only one of the two cases is possible.) In any case, the first two elements are two adjacent numbers, and the third element is a neighbor of this "segment," either 1 less than the smaller number or 1 more than the larger number.

Similarly, we get that the first $i$ elements are $i$ adjacent numbers, and the $(i+1)$-th element is either 1 less than the minimum of these numbers or 1 more than the maximum.

Thus, to each sequence - starting from the second element - we can assign a sequence of 0s and 1s. The 0 in the $(i+1)$-th position indicates that the number 1 less than the minimum of the first $i$ numbers is placed in the $(i+1)$-th position, and the 1 indicates that the number 1 more than the maximum of the first $i$ numbers is placed in the $(i+1)$-th position.

Thus, we have assigned an $(n-1)$-length 0-1 sequence to a suitable arrangement of the first $n$ numbers. This assignment is bijective if we can determine the first element from this 0-1 sequence, since then the continuation is unique.

Notice that the first element, $k$, is 1 more than the number of zeros in the sequence, since then we have $(k-1)$ possibilities to decrease the minimum of the segment by 1.

The number of $(n-1)$-length 0-1 sequences, as is well known, is $2^{n-1}$, so this is also the number of the arrangements asked for in the problem.

Tóth Ágnes (Hajdúszoboszló, Hőgyes E. Gimn., 9th grade)