9.5 In some cells of a $10 \times 10$ table, crosses are placed such that each of them is the only one either in its row or in its column. What is the maximum number of crosses that can be in such a table? Justify your answer.
Solution. We will place crosses in all cells of the first row and the first column, excluding the top-left cell - a total of 18 crosses. Then each cross in the first row is unique in its column, and each cross in the first column is unique in its row. Therefore, it is possible to place 18 crosses.

We will show that if we place 19 crosses (or more), some cross will not be unique in its row or column. Assume the opposite. We will call rows and columns simply lines. We will assign to each cross the line in which it is unique (if there are two such lines, then any one of them). Then different crosses are assigned different lines; there are 19 crosses and 20 lines, so all lines, except one, are assigned to some cross, meaning they contain exactly one cross. The only unassigned line contains no more than 10 crosses (more cannot fit on it). The total number of pairs cross - line, where the line contains the cross, will be no more than $19+10=29$. But in reality, there are $19 \cdot 2=38$ - a contradiction.

Answer: 18 crosses.

| PRESENT IN THE SOLUTION | SCORE |
| :--- | :---: |
| Correct and justified answer | 7 points |
| Correct proof that 19 crosses cannot be placed in the table (in the absence of proof that 19 can) | 4 points |
| Correct example of placing 18 crosses (or proof of the existence of such an example) | 2 points |
| Examples of placing fewer than 18 crosses and/or proofs that there cannot be 20 or more crosses | 0 points |