9. On a white checkered board of size $25 \times 25$ cells, several cells are painted black, with exactly 9 cells painted black in each row and each column. What is the smallest $k$ such that it is always possible to repaint $k$ cells to white in such a way that it is impossible to cut out a black $2 \times 2$ square? (S. Berlov)
Solution. Evaluation. Note that if 9 cells are shaded in a row, then four of them can be repainted so that no two shaded cells are adjacent: it is enough to renumber the shaded cells from left to right and repaint the cells with even numbers. If such repainting is done with all even rows, then 48 cells will be repainted and there will be no shaded $2 \times 2$ squares, since there will be no two adjacent shaded cells in one even row.

![](https://cdn.mathpix.com/cropped/2024_05_06_0534390b892a5ed92d35g-1.jpg?height=314&width=308&top_left_y=1808&top_left_x=1662)

Example. Let's shade non-overlapping squares along the main diagonal: the first with a side of 9 and two with a side of 8 - and the cells located along the unshaded main diagonal of the $16 \times 16$ square containing the $8 \times 8$ squares. Then on the board, it will be possible to highlight 48 non-overlapping $2 \times 2$ squares, all cells of which are shaded. Therefore, in this example, at least 48 cells need to be repainted.