5. Given a square table of size $2021 \times 2021$. Each of its cells is colored in one of $n$ colors. It is known that for any four cells of the same color located in the same column, there are no cells of the same color to the right of the top one and to the left of the bottom one. What is the smallest $n$ for which this is possible?
Answer: 506.

Solution. Consider some specific color (say, blue). In each column, mark the three lower blue cells with a cross, and the rest with a zero (if there are fewer than four blue cells in the column, mark all cells with a cross). Note that in any row, there is no more than one blue cell with a zero (otherwise, for the leftmost of them, the condition of the problem is violated). Therefore, there are no more than 2021 blue cells with a zero. In addition, the number of blue cells with a cross does not exceed $3 \cdot 2021$. Thus, the total number of blue cells does not exceed $2021 + 3 \cdot 2021 = 4 \cdot 2021$. These arguments are valid for any color. Therefore, the total number of colors is not less than

$$
\frac{2021^{2}}{4 \cdot 2021} = \frac{2021}{4} = 505.25
$$

Thus, $n \geqslant 506$.

We will show that $n=506$ is achievable. Sequentially number all diagonals from bottom to top, running from northwest to southeast, with numbers from 1 to 4041. Paint the first four diagonals in the first color, the next four in the second color, and so on in a cycle (so after the 506th color, the first color will follow again). We will check that this coloring satisfies the condition of the problem. Note that no color is used more than twice, since $506 \cdot 4 \cdot 2 = 4048 > 4041$. Let the $k$-th color appear twice. In the first block, the topmost cell of this color will be in the row with number $4k$. In the second block, the bottommost cell of this color is in the row with number

$$
4(506+k-1)+1-2020 = 4k+1
$$

Thus, cells of the same color from different blocks cannot be in the same row.

## Variant 4