11.3. What is the maximum number of colors needed to color all cells of a 4 by 4 square so that for every pair of different colors, there are two cells of these colors that are either in the same row or in the same column of the square?
Answer: In 8 colors.

Solution. If the cells were painted in 9 or more colors, there would be a color in which only one cell is painted. There are only 6 cells located in the same row or column with it, so there are no more than 6 other colors forming a pair with it, as required by the condition - a contradiction. Therefore, the cells can be painted in no more than 8 colors.

Let's provide two essentially different examples of the required coloring in 8 colors, with each color being used for exactly two cells of the square.

| 5 | 6 | 3 | 8 |
| :--- | :--- | :--- | :--- |
| 3 | 4 | 2 | 7 |
| 2 | 1 | 6 | 5 |
| 1 | 7 | 8 | 4 |


| 6 | 7 | 8 | 3 |
| :--- | :--- | :--- | :--- |
| 4 | 5 | 2 | 6 |
| 2 | 3 | 4 | 5 |
| 1 | 1 | 7 | 8 |

Grading criteria. It is proven that the cells cannot be painted in more than 8 colors (i.e., an upper bound on the number of colors is established): 3 points.

A correct example of the required coloring in 8 colors is explicitly provided: 3 points. Justification of it and description of the construction idea are not required.

Both the example and the estimate are present: 7 points.