
4. The Crocodile thought of four unit squares of a $2018 \times 2018$ forming a rectangle with sides 1 and 4 . The Bear can choose any square formed by 9 unit squares and ask whether it contains at least one of the four Crocodile's squares. What minimum number of questions should he ask to be sure of at least one affirmative answer?

The answer is $\frac{673^{2}-1}{2}=226464$.


Solution. We call checked any square chosen by the Bear, and all its unit squares. The position of a unit square in the table can be defined by the numbers of its row and column, that is, the square $(x, y)$ is in the $x$-th row and $y$-th column.

First we prove that $\frac{673^{2}-1}{2}$ questions is enough even on a $2019 \times 2019$ table. Let us divide this table into $3 \times 3$ squares and apply chess colouring to these large squares so that the corners are white. Thet it is enough to check all the black $3 \times 3$ squares: no row or column contains four consecutive white squares.

To prove that we need so many questions, we select all the unit squares with coordinates $(3 m+1,3 n+1)$, where $0 \leqslant m, n \leqslant 672$. A $3 \times 3$ square obviously can not contain two selected unit squares. On the other hand, if two selected squares lie at distance 3 (i.e., one of them is $(x, y)$, and another is $(x, y+3)$ or $(x+3, y)$ ), the Bear must check at least one of these two squares (because if neither is checked, then so are the two unit squares between them, and the Crocodile can place his rectangle on the unchecked squares).

Thus it is enough to produce $\frac{673^{2}-1}{2}$ pairs of selected unit squares at distance 3 . One can take pairs $(6 k+1,3 n+1)$, $(6 k+4,3 n+1), 0 \leqslant k \leqslant 335,0 \leqslant n \leqslant 672$, and $(2017,6 n+1),(2017,6 n+4), 0 \leqslant n \leqslant 335$.
