$3+$  [ Examples and counterexamples. Constructions]

In a square table of size $100 \times 100$, some cells are shaded. Each shaded cell is the only shaded cell either in its column or in its row. What is the maximum number of cells that can be shaded

#
Example. We will color all the cells of one row and all the cells of one column, except for their common cell. In this case, the condition of the problem is satisfied and exactly 198 cells are colored.

Evaluation. For each colored cell, we will highlight the line (row or column) in which it is the only colored one. In this case, no more than 99 rows can be highlighted. Indeed, if 100 rows are highlighted, then each colored cell is the only one in its row, but then there are no more than 100 colored cells. Similarly, no more than 99 columns can be highlighted. Therefore, the number of highlighted lines, and thus the number of colored cells, does not exceed 198.

## Answer

198.

Send a comment