6. In a $4 \times 4$ square, cells are colored in several colors such that in any $1 \times 3$ rectangle, there are two cells of the same color. What is the maximum number of colors that can be used?
Solution. Maximum 9 colors. See example in the picture. We will prove that more is not possible. Any row (row or column) gives a maximum of three colors, so the first row + first column will give a maximum of $3+3-1=5$ colors.

We will prove that the remaining $3 \times 3$ square will give a maximum of 4 colors. Indeed, suppose we used 5 colors in it. Since in one row there are no more than two different colors, there will be two rows in which 4 different colors are used, 2 colors in each row. Then in the remaining row, there will be at least one cell of the fifth color. In the column containing this cell, all cells will be of different colors. Contradiction.

Thus, on the entire board, there are no more than $4+5=9$ different colors.

Criteria. Full solution (there is an estimate and there is an example) - 7 points.

Of these:

There is an example for 9 colors - 2 points.

Full proof of the estimate - 5 points, of which: 2 points for one row + one column and 3 points for the proof that the $3 \times 3$ square will give a maximum of 4 colors.

![](https://cdn.mathpix.com/cropped/2024_05_06_0bb07e0f32a6824c13e1g-2.jpg?height=303&width=292&top_left_y=1670&top_left_x=1727)