4. The cells of a $20 \times 20$ table are painted in $n$ colors, and there are cells of each color. In each row and each column of the table, no more than six different colors are used. What is the largest $n$ for which this is possible?
Answer: 101.

Solution. Suppose there is a coloring with 102 colors. Then there are two rows that together use at least 12 colors (otherwise, the total number of colors does not exceed $11+5 \cdot 18=101$). Let's assume for definiteness that these are the first and second rows. By the condition, no more than six different colors are present in each row. Therefore, exactly six colors are used in both the first and second rows, and all these colors are different. We will call the colors used in the first two rows dark, and the rest light. Now consider the columns of the table. In each of them, there are no more than four light colors, since the two top cells are painted in different dark colors. Then the total number of light colors used in the table does not exceed $4 \cdot 20=80$ and 12 dark colors. Thus, the total number of colors does not exceed $80+12=92<102$, which is impossible.

A coloring with 101 colors is given below. Empty cells are painted in the 100th color.

| 0 | 1 | 2 | 3 | 4 |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
| :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: |
|  | 5 | 6 | 7 | 8 | 9 |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
|  |  | 10 | 11 | 12 | 13 | 14 |  |  |  |  |  |  |  |  |  |  |  |  |  |
|  |  |  | 15 | 16 | 17 | 18 | 19 |  |  |  |  |  |  |  |  |  |  |  |  |
| $\cdots$ | $\cdots$ | $\cdots$ | $\cdots$ | $\cdots$ | $\cdots$ | $\cdots$ | $\cdots$ | $\cdots$ | $\cdots$ | $\cdots$ | $\cdots$ | $\cdots$ | $\cdots$ | $\cdots$ | $\cdots$ | $\cdots$ | $\cdots$ | $\cdots$ | $\cdots$ |
|  |  |  |  |  |  |  |  |  |  |  |  |  |  |  | 75 | 76 | 77 | 78 | 79 |
| 80 |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  | 81 | 82 | 83 | 84 |
| 85 | 86 |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  | 87 | 88 | 89 |
| 90 | 91 | 92 |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  | 93 | 94 |
| 95 | 96 | 97 | 98 |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  | 99 |