9.4. What is the maximum number of colors in which all cells of a 4 by 4 square can be painted so that any 2 by 2 square of cells necessarily contains at least two cells of the same color?
Answer: In 11 colors.

Solution. We will prove that the maximum number of colors under the conditions of the problem does not exceed 11. Consider in a 4x4 square five 2x2 squares: four corner ones and the central one. The corner 2x2 squares do not intersect, and the central one shares one common cell with each of the corner ones. According to the condition, each corner 2x2 square contains cells of no more than three different colors, totaling no more than 12. But if there are no repeating colors among these four sets of three colors in the corner 2x2 squares, then the central 2x2 square must contain cells of four different colors - one from each set of three, which contradicts the condition. Therefore, the total number of different colors in which the cells of the 4x4 square are painted does not exceed 12-1=11. If, however, in at least one of the corner 2x2 squares no more than two different colors are used, then the total number of different colors is immediately no more than 11.

An example of coloring a 4x4 square in 11 colors, satisfying the condition of the problem, looks like this: the bottom horizontal row of the square is painted in different colors $1,2,3$ and 4, the second horizontal row - entirely in color 5, the third horizontal row in different colors $6,7,8$ and 9, and the fourth horizontal row - in colors $10,7,11,9$.

Grading criteria. ($\cdot$) Proof of the maximum of 11 colors: 4 points, ($\cdot$) If the case where in one of the corner 2x2 squares no more than two different colors are used is not considered at all in the proof of the maximum of 11 colors: minus 1 point. ($\cdot$) Example of a correct coloring in 11 colors: 3 points.