Muamiev D:

What is the maximum number of colors in which all cells of a $10 \times 10$ board can be painted so that in each row and each column there are cells of no more than five different colors?
An example of coloring in 41 colors is shown in the figure (unmarked cells are colored in the 41st color).

| 1 | 2 | 3 | 4 |  |  |  |  |  |  |
| :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: |
|  | 5 | 6 | 7 | 8 |  |  |  |  |  |
|  |  | 9 | 10 | 11 | 12 |  |  |  |  |
|  |  |  | 13 | 14 | 15 | 16 |  |  |  |
|  |  |  |  | 17 | 18 | 19 | 20 |  |  |
|  |  |  |  |  | 21 | 22 | 23 | 24 |  |
|  |  |  |  |  |  | 25 | 26 | 27 | 28 |
| 32 |  |  |  |  |  |  | 29 | 30 | 31 |
| 35 | 36 |  |  |  |  |  |  | 33 | 34 |
| 38 | 39 | 40 |  |  |  |  |  |  | 37 |

Evaluation. If in each row there are no more than four colors, then the total number of colors is no more than 40. Let row A contain five colors. If in each remaining row there are no more than four colors not found in A, then the total number of colors is no more than \(5 + 4 \cdot 9 = 41\).

Suppose there is a row B in which five colors different from the colors in row A appear. Let's call the 10 colors

![](https://cdn.mathpix.com/cropped/2024_05_06_ed128c2d5b4d71db92ebg-34.jpg?height=52&width=989&top_left_y=2518&top_left_x=20)

Now, in each column, there are at least two old colors (in rows A and B), so there are no more than three new colors. Therefore, in total, there are 10 old and no more than 30 new colors, totaling no more than 40.

## Answer

## Problem