Problem 5. Each cell of a $3 \times 3$ table is painted in one of three colors such that cells sharing a side have different colors. Among all possible such colorings, find the proportion of those in which exactly two colors are used.
Answer: $1 / 41$.

Solution. The central cell can be colored in any of the three colors, let's call this color $a$. Each of the four cells that share a side with the central cell can be colored in any of the two remaining colors. Let the cell above the central one be colored in color $b$. The third color will be called $c$. Consider all possible ways to color the cells that share a side with the central cell, and encode them with strings of letters $b$ and $c$, which start with the letter $b$ and then correspond to the colors of these cells, traversed counterclockwise. For example, the coloring

![](https://cdn.mathpix.com/cropped/2024_05_06_120492c4c27caef101b6g-2.jpg?height=174&width=203&top_left_y=1689&top_left_x=938)

will be encoded by the string $b c c b$.

Consider any corner cell. If the two cells that share a side with it are colored the same, then the corner cell can be colored in two ways. If these two cells are colored differently, then the corner cell can be colored in only one way. We will construct a table in which, for each of the 8 obtained encoding strings, we will indicate the number of colorings of the corner cells.

| $b b b b$ | 16 | $b b c b$ | 4 | $b c b b$ | 4 | $b c c b$ | 4 |
| :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: |
| $b b b c$ | 4 | $b b c c$ | 4 | $b c b c$ | 1 | $b c c c$ | 4 |

Thus, the desired number of colorings is the product of the number of ways to color the central cell, the number of ways to color the cell above the central one, and the sum of the numbers in the constructed table: $3 \cdot 2 \cdot(16+6 \cdot 4+1)=246$.

The number of two-color tables is 6, since the color of the central cell in this case coincides with the color of the corner cells, and for the cells that share a side with the central cell, there are always two possible options. Hence, the desired ratio is $\frac{1}{41}$.

Answer to variant 2: 40/41.