1. Pete and Vasya are playing the following game. Pete marks $k$ cells on a $9 \times 9$ board, after which Vasya places a $1 \times 4$ rectangle on the board and tells Pete which of the marked cells he has covered (the rectangle can be rotated). Vasya wins if Pete cannot uniquely determine the position of the rectangle. For what smallest $k$ can Pete mark the cells in such a way that Vasya cannot win?
Answer: 40.

Solution. We will show that it is necessary to mark at least 40 cells. Consider 5 consecutive cells: $A|B| C|D| E$. Petya must mark at least one of the cells $A$ and $E$. Indeed, if Petya does not mark cells $A$ and $E$, then he will not be able to distinguish the placement of the rectangle on cells $A B C D$ from the placement on cells $B C D E$. Therefore, at least one of any cells, spaced three apart (both horizontally and vertically), must be marked. A strip $1 \times 8$ can be divided into four pairs of such cells, so there must be at least four marked cells in it. Note that from a $9 \times 9$ board, 10 non-overlapping strips $1 \times 8$ can be cut out (9 horizontal and one vertical). Therefore, there must be at least 40 marked cells. An example with 40 marked cells is shown in the figure.

![](https://cdn.mathpix.com/cropped/2024_05_06_9304f7a3bc6f36cb1f9ag-24.jpg?height=331&width=342&top_left_y=954&top_left_x=914)