Problem 7.8. The cells of a $50 \times 50$ table are colored in $n$ colors such that for any cell, the union of its row and column contains cells of all $n$ colors. Find the maximum possible number of blue cells if

(a) (1 point) $n=2$

(b) (3 points) $n=25$.
Answer: (a) 2450. (b) 1300.

Solution. We will prove that the number of cells of any color $A$ present in the coloring is no less than 50. Suppose this is not the case, and the number of cells of color $A$ is no more than 49. Then there exists a row without cells of color $A$, and there also exists a column without cells of color $A$. But then for the cell at the intersection of these row and column, the condition is not satisfied, which is a contradiction. Therefore, the number of cells of any color $A$ is no less than 50.

(a) Since the number of cells not blue is no less than 50, the number of blue cells is no more than $50 \cdot 50 - 50 = 2450$. Exactly 2450 blue cells can be present, for example, if all cells in the bottom row are red, and all other cells in the table are blue.

(b) Since the number of cells of any non-blue color is no less than 50, the number of blue cells is no more than $50 \cdot 50 - 24 \cdot 50 = 1300$. Exactly 1300 blue cells can be present, for example, if all cells in the first 26 rows of the table are blue, and each of the remaining 24 rows consists of cells of a single color, and the colors of these 24 rows are different.

## 7th grade