4. On a $50 \times 50$ chessboard, Petya places 50 non-attacking rooks, and Vasya selects a $k \times k$ square ($k \leqslant 50$) on the board. For which $k$ can Vasya always choose a square that does not contain any rooks, regardless of Petya's actions?
Answer: For $k \leqslant 7$.

Solution. We will show how Vasya can choose a $7 \times 7$ square. Notice that at least one corner of the $50 \times 50$ board is not occupied by a rook. Let's assume, for definiteness, that this is the top right corner. Then in the topmost row and the rightmost column, there is a rook. We will divide the remaining part of the board into $7 \times 7$ squares starting from the bottom left corner. We will get $7^{2}$ squares, in which there are no more than $7^{2}-1$ rooks. Therefore, some square is empty, and Vasya can choose it.

We will show how to place 50 rooks so that there is not even an empty $8 \times 8$ square. We will number the rows and columns of the $50 \times 50$ board with numbers from 0 to 49. We will place rooks in cells with coordinates $(8x + y, x + 8y)$ for all such non-negative integers $x$ and $y$ that fit on the board. Then it is easy to see that for any placement of an $8 \times 8$ square, it will contain at least one rook. Note that $0 \leqslant x \leqslant 6$ and $0 \leqslant y \leqslant 6$. We will show that among them, there are no rooks standing in the same row. Indeed, if two rooks are on the same vertical, then $8x + y = 8x' + y'$, from which $y' - y$ is divisible by 8, and thus $y = y'$, and then $x = x'$. Similarly, it can be verified that two rooks will not be on the same horizontal. Since $0 \leqslant x, y \leqslant 6$, no more than 49 rooks are placed. We will sequentially add the missing number of rooks to the free rows and columns and obtain the required placement.