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

![](https://cdn.mathpix.com/cropped/2024_05_08_22585010b2534c7ab9ebg-26.jpg?height=340&width=1081&top_left_y=1857&top_left_x=497)

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). #
Let $M_{n}$ denote the number of all possible routes of duration $n$ minutes. Each such route consists of exactly $n$ segments (a segment is either $A B$, $B A$, or a 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$.

One can reach point $B$ in a minute either from point $A$ or from point $B$, so $M_{n, B}=M_{n-1}$.

One can reach point $A$ in a minute only from point $B$, so $M_{n, A}=M_{n-1, B}=M_{n-2}=M_{n-2, A}+M_{n-2, B}=M_{n-2, A}+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,

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

## Answer

34 routes.

Submit a comment