5. A line in which all natural numbers from 1 to $n$ are written exactly once will be called evident if for any $k$ one of the following conditions is met:

(a) $k$ is written first;

(b) among the numbers written to the left of $k$, there is either $(k-1)$ or $(k+1)$.

Find the number of all evident strings of length $n$.
Solution. We will prove that non-adjacent strings of length $n$ are in one-to-one correspondence with strings of zeros and ones of length $n-1$. From this, it will follow that there are $2^{n-1}$ such strings.

Take an arbitrary number $k$ that is not in the first position, and draw arrows from it to the numbers $k-1$ and $k+1$ that are to its left. From all numbers except the first, at least one arrow goes out, so there are at least $n-1$ arrows. On the other hand, no number except the first can have two arrows entering it. If the first number is 1 or $n$, then no more than one arrow can enter it. In 1 and $n$, which are not in the first position, no arrows can enter. Thus, there are no more than $n-1$ arrows. Therefore, there are exactly $n-1$ arrows. From this, it follows that the entire directed graph is the union of two chains (one of which can have zero length), converging to the first number. In one of the chains, the numbers are always decreasing and it has the form $n \rightarrow n-1 \rightarrow \ldots$, and in the other, they are increasing and it has the form $1 \rightarrow 2 \rightarrow \ldots$ Replace each number except the first with one if it belongs to the first chain, and with zero otherwise. We get a string of zeros and ones of length $n-1$.

It is now not difficult to provide the reverse construction. Let us be given a string of $n-1$ zeros and ones, and let there be $k$ ones in it $(k=0,1, \ldots, n-1)$. Consider all the ones and, moving from right to left, replace them with $n, n-1, n-2, \ldots, n-k+1$ (for $k=0$, we get an empty set of numbers). Moving from right to left, replace the zeros with $1,2, \ldots, n-k-1$ (for $k=n-1$, we get an empty set of numbers). Append the unused number $n-k$ at the beginning. It is easy to see that such a string is non-adjacent.

Answer. $2^{n-1}$.

VIII Team and Individual Tournament "Mathematical Pentathlon"

$2-7$ November 2015, Moscow

## Oral Olympiad in Combinatorics

## Senior League