10.6. A square $100 \times 100$ is divided into squares $2 \times 2$. Then it is divided into dominoes (rectangles $1 \times 2$ and $2 \times 1$). What is the smallest number of dominoes that could end up inside the squares of the division?

(C. Berlov)

#
# Answer. 100.

Solution. Example. We will divide the top and bottom horizontals into horizontal dominoes - they will end up in $2 \times 2$ squares. The remaining rectangle $98 \times 100$ will be divided into vertical dominoes - they will not end up in $2 \times 2$ squares.

Estimate. Consider the squares $A_{1}, A_{3}, \ldots, A_{99}$ of sizes $1 \times 1, 3 \times 3, \ldots, 99 \times 99$, whose lower left corner coincides with the lower left corner of the original $100 \times 100$ square. For each of the squares $A_{i} (i=1,3,5, \ldots, 99)$, there is a domino $X_{i}$ that intersects its side (since squares of odd area cannot be divided into dominoes). It is easy to see that $X_{i}$ lies within a $2 \times 2$ square from the division.

Similarly, considering the squares $B_{1}, B_{3}, \ldots, B_{99}$ of sizes $1 \times 1, 3 \times 3, \ldots, 99 \times 99$, whose upper right corner coincides with the upper right corner of the original $100 \times 100$ square, we find another 50 dominoes $Y_{j} (j=1,3,5, \ldots, 99)$ that we need.

This completes the solution (it is obvious that all dominoes $X_{1}, X_{3}, \ldots, X_{99}, Y_{1}, Y_{3}, \ldots, Y_{99}$ are distinct).

Remark. We will present a slightly different proof of the estimate.

Suppose that no more than 99 dominoes ended up inside the $2 \times 2$ squares.

Draw 50 vertical grid lines $v_{1}, v_{3}, v_{5}, \ldots, v_{99}$ such that $v_{i}$ separates $i$ columns on the left. It is easy to see that any domino intersected by one of the lines $v_{1}, v_{3}, v_{5}, \ldots, v_{99}$ is suitable for us. Each vertical line intersects an even number of dominoes, since there is an even number of cells to the left of this line. Therefore, among the lines $v_{1}, v_{3}, v_{5}, \ldots, v_{99}$, there is a line $v_{i}$ that does not intersect any dominoes, otherwise we would have already found at least $2 \cdot 50 = 100$ dominoes that we need. We will conduct a similar reasoning for 50 horizontal grid lines $h_{1}, h_{3}, h_{5}, \ldots, h_{99}$ and find among them a line $h_{j}$ that does not intersect any dominoes. But $v_{i}$ and $h_{j}$ divide the board into regions with an odd number of cells, so at least one of these two lines must intersect a domino. Contradiction.

Comment. Only the example -1 point.

Proved only that the number of dominoes is even - 0 points.

Criteria for a solution with paths of good (lying in $2 \times 2$ squares) dominoes are as follows.

Only the idea of paths -0 points.

Proved that next to each good domino there is at least one more good one, and there is an idea of constructing a path from these dominoes -1 point.

For a complete solution of the problem, it remains to solve the problem of looping and crossing paths of dominoes, and there is a division into regions by shifting the grid and constructing a graph with even degrees of vertices, and there is an example - a total of 3 points.

For a complete solution of the problem, it remains to solve the problem of looping and crossing paths of dominoes, and there is a division into regions by shifting the grid and constructing a graph with even degrees of vertices, and there is an example - a total of 5 points.

An attempt to close the problem of looping by the fact that in this case an area of odd area is obtained, WITHOUT a complete and correct proof -0 points.

The problem is solved, but there are minor errors in the proof of the intersection of paths -6 points.

Criteria for a solution with a division into regions, each of which contains a good (lying in a $2 \times 2$ square) domino, are as follows.

There is a division into regions, in each of which there is indeed at least one good domino (but this is not proved) -1 point.

There is a division into regions and a proof that the problem is solved if we prove that in each region there is at least one good domino; but this statement is not proved or contains significant errors - a total of 3 points.

There is a division into regions and a proof that the problem is solved if we prove that in each region there is at least one good domino, but this statement is proved with minor errors - 5 or 6 points.

Attempts to count the number of boundaries of $2 \times 2$ squares (internal or external), not leading to a correct solution - 0 points.