Shapovalov A.V.

What is the maximum number of colors that can be used to color the cells of an $8 \times 8$ chessboard so that each cell shares a side with at least two cells of the same color?
Let's divide the board into 16 squares of $2 \times 2$ and color each square with a different color. This coloring with 16 colors satisfies the condition.

It is impossible to achieve more colors. Indeed, if there are no more than three cells of a certain color, then only one of them can share a side with two cells of the same color (see figure).
![](https://cdn.mathpix.com/cropped/2024_05_06_04ea0aec75eb28164af1g-02.jpg?height=226&width=536&top_left_y=796&top_left_x=767)

If, however, there are at least four cells of each color, then there can be no more than sixteen different colors.

## Answer

In 16 colors.