9.3. We consider all possible tilings of an 8 by 8 chessboard with dominoes, each consisting of two adjacent squares. Determine the maximum natural number \( n \) such that for any tiling of the 8 by 8 board with dominoes, one can find some rectangle composed of \( n \) squares of the board that does not contain any domino in its entirety. The lengths of the sides of the rectangle in squares can be any natural numbers, starting from one.
Answer. $n=4$.

Solution. 1) We will prove that $n \leq 4$. Consider the following tiling of an 8 by 8 chessboard with dominoes. Divide the board into 2 by 2 squares, color each of them in red and blue in a checkerboard (relative to the 4 by 4 board) pattern, and divide the red squares into pairs of horizontal dominoes, and the blue squares into pairs of vertical dominoes. Any rectangle with an area greater than 4 either contains a 1 by 5 rectangle or a 2 by 3 rectangle. It is easy to verify that for the considered tiling, a 1 by 5 rectangle or a 2 by 3 rectangle in any position on the board contains at least one entire domino.

2) We will prove that for any tiling of an 8 by 8 board with dominoes, one can find some rectangle of area 4, composed of cells, that does not contain any entire domino. Consider the domino in the tiling that contains cell d4; we can, by rotating the board if necessary, assume it is horizontal. We will consider in detail the case where it consists of cells c4, d4; the case where it consists of cells d4, e4 is analogous. Consider the cells c3, d3 and c5, d5. If at least one of these cells, say c3 (other cases are analogous), lies in a horizontal domino of the tiling, then the vertical rectangle c2, c3, c4, c5 does not contain any entire domino of the tiling. If all these cells lie in vertical dominoes of the tiling, then the dominoes containing c3 and d3 are vertical, so the rectangle b3, c3, d3, e3 does not contain any entire domino of the tiling. Note that by choosing cell d4 to start the reasoning, we ensure that the selected 1 by 4 strip cannot extend beyond the board.

Grading criteria. ($\cdot$) If the point 1) that $n \leq 4$ is proven: 2 points. ($\cdot$) If the point 2) that one can always find some suitable rectangle of area 4: 5 points. ($\cdot$) If an example of a tiling is provided where any rectangle with more than 4 cells always contains an entire domino, and it is correct, the score is not reduced for lack of meticulous verification. ($\cdot$) In a generally correct reasoning about selecting a 1 by 4 strip of cells that does not contain any entire domino, the possibility of extending beyond the edge of the board is not considered: minus 2 points. ($\cdot$) In the reasoning, the possibility of the sought rectangle extending beyond the edge of the board is allowed: the solution is given 0 points.