18. The figure shows a track scheme for karting. The start and finish are at point $A$, and the kart driver can make as many laps as they want, returning to the starting point.

![](https://cdn.mathpix.com/cropped/2024_05_06_69e0be57d9eb74bf0932g-14.jpg?height=402&width=1288&top_left_y=867&top_left_x=384)

The young driver Yura spends one minute on the path from $A$ to $B$ or back. Yura also spends one minute on the loop. The loop can only be driven counterclockwise (arrows indicate possible directions of movement). Yura does not turn back halfway and does not stop. The race duration is 10 minutes. Find the number of possible different routes (sequences of passing sections). #
# Solution.

Let $M_{n}$ be the number of all possible routes of duration $n$ minutes. Each such route consists of exactly $n$ segments (a segment is the segment $A B, B A$ or the loop $B B$).

Let $M_{n, A}$ be the number of such routes ending at $A$, and $M_{n, B}$ be the number of routes ending at $B$.

A point $B$ can be reached in one minute either from point $A$ or from point $B$, so $M_{n, B}=M_{n-1}$.

A point $A$ can be reached in one minute only from point $B$, so $M_{n, A}=M_{n-1, B}=M_{n-2}$. Therefore,

$$
M_{n, A}=M_{n-2}=M_{n-2, A}+M_{n-2, B}=M_{n-4}+M_{n-3}=M_{n-2, A}+M_{n-1, A}
$$

Additionally, note that $M_{1, A}=0, M_{2, A}=1$. Thus, the numbers $M_{n, A}$ form the sequence $0,1,1,2,3,5,8,13,21,34, \ldots$

The number $M_{10, A}$ is 34 - the ninth Fibonacci number ${ }^{1}$.

Answer: 34.