# Task 8. (16 points)

Vova was playing with old domino tiles, on which all the dots had worn off, making them indistinguishable. Each tile is a $2 \times 1$ rectangle, and their total number is 24. Vova decided to arrange the tiles in a new pattern each day to form a $2 \times 12$ path, ensuring that the pattern of the arrangement never repeats. How many days can Vova continue arranging the tiles in this way, making one arrangement per day, until all possible arrangements are exhausted?
# Solution.

We will assume that the paths are arranged horizontally, with the longer side along the x-axis. The dominoes in such paths can be of two types: vertical (placed across the path) and horizontal, placed along the path.

Each vertical domino "cuts" the path and divides it into two parts, to the right and left of itself.

Each horizontal domino must have a paired horizontal domino, together forming a $2 \times 2$ square.

Indeed, if there were a pair of horizontal dominoes that did not form a square (i.e., were arranged as shown in the figure), then both parts of the path to the right and left of this pair of dominoes would contain an odd number of dominoes and could not be covered by dominoes.

![](https://cdn.mathpix.com/cropped/2024_05_06_c119ef58862eb5cdf0f6g-7.jpg?height=314&width=854&top_left_y=1571&top_left_x=1132)

Let $F(n)$ be the number of possible tilings of a path of size $2 \times n$ with dominoes of size $2 \times 1$. Then, obviously, $F(1)=1, F(2)=2, F(3)=3$.

Each tiling of a path $2 \times n$ has at its right end either a vertical domino (removing which can yield a tiling of a path $2 \times(n-1)$) or a pair of horizontal dominoes (removing which can yield a tiling of a path $2 \times(n-2))$. This fact justifies the formula: $F(n)=F(n-1)+F(n-2)$, i.e., the sequence $F(n)$ is the Fibonacci sequence. Answer: $F(12)=233$.

| Full solution. | + | 16 |
| :---: | :---: | :---: |
| The answer is correct. All main logical steps of the solution are provided. Some individual conclusions lack rigorous justification. | $\pm$ | 12 |
| All main logical steps of the solution are provided. Some individual conclusions lack rigorous justification. A computational error or typo may result in an incorrect answer. | $+/ 2$ | 8 |
| The solution is generally incorrect or incomplete, but contains some progress in the right direction. The answer is missing. | $\mp$ | 3 |
| The solution does not meet any of the criteria described |  |  |
| above. |  |  |