4. The cells of an $n \times n$ square are painted in $n$ colors, with $n$ cells of each color. For which $n$ can the square be painted in such a way that in each row and each column there are cells of exactly two colors?
Answer: 2, 3, 4. Sketch of the solution.

Examples for 2, 3, and 4 are shown in

the figure on the right. Colors

are numbered by numbers.

![](https://cdn.mathpix.com/cropped/2024_05_06_62561d6f0f1123503915g-2.jpg?height=212&width=548&top_left_y=692&top_left_x=2165)

Estimation. Let $n \geq 5$ and it was possible to color the square in the required manner. We will compile a list of colors that appear in the rows, with exactly two colors in each. There will be a total of $2 n$ colors in the list. Each color must appear in at least two rows, because if it appears in only one row, and a total of $\mathrm{n}$ cells are colored, then all cells in that row will be of the same color. This means they will occupy at least $2 n$ positions. From this, it follows that each color is used in two rows, since there are exactly $2 n$ positions for their recording in the rows. Consider the first column, which contains two colors, and since there are at least five cells, at least three cells are colored in one color. This means that this color appears in three rows, which contradicts the previously proven statement. Therefore, coloring is impossible for $n \geq 5$. The case $n=1$ is obviously impossible.

Criteria. Correct answer with three examples: 2 points.