A $20 \times 20$ chessboard has some squares occupied by pieces. A piece can be removed from the board if at least half of the squares in its row or column are empty. What is the minimum number of pieces needed so that, when placed appropriately, none of them can be removed?
Solution. $11 \cdot 11$ = 121 dolls can be placed according to the conditions, for example, by placing them in the lower left $11 \times 11$ square. In this case, in any row or column that contains a doll, there are 11, which is more than half of the squares, so none can be removed from there.

We will show that 120, or fewer dolls, are not sufficient. If there were only this many, then in at most 10 rows there could be at least 11 dolls. In the remaining 10 rows, there can be at most 10 dolls each. If there were any dolls in these rows, one could be removed from there, so there cannot be any dolls in them. However, this means that no matter which doll we look at on the board, there must be 10 empty spaces in its column, so it can be removed.