Problem 4. Each cell of a $3 \times 3$ table is painted in one of three colors such that cells sharing a side have different colors, and not all three colors need to be used. How many such colorings exist?
Answer: 246.

Solution. The central cell can be painted in any of the three colors, let's call this color $a$. Each of the four cells that share a side with the central one can be painted in any of the two remaining colors. Let the cell located above the central one be painted in color $b$. The third color we will call $c$. Consider all possible ways to paint the cells that share a side with the central one, 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 painting

|  | $b$ |  |
| :--- | :--- | :--- |
| $c$ | $a$ | $b$ |
|  | $c$ |  |

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 painted in the same color, then the corner cell can be painted in two ways. If these two cells are painted in different colors, then the corner cell can be painted 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 ways to paint 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 paint the central cell, the number of ways to paint the cell located above the central one, and the sum of the numbers in the constructed table: $3 \cdot 2 \cdot(16+6 \cdot 4+1)=246$.