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

Solution. We will show that at least 48 cells are marked. First, let's check the following statement: among any two cells that are two cells apart horizontally, vertically, or diagonally, at least one is marked. Indeed, consider a $3 \times 3$ square:

![](https://cdn.mathpix.com/cropped/2024_05_06_9304f7a3bc6f36cb1f9ag-36.jpg?height=125&width=120&top_left_y=760&top_left_x=1022)

If Petya does not mark cells $B$ and $F$, then he cannot distinguish the placement of the figure on cells $B C D E$ from the placement on cells $C D E F$. If Petya does not mark cells $A$ and $E$, then he cannot distinguish the placement of the figure on cells $A B C D$ from the placement on cells $B C D E$.

Now we will show that in any $4 \times 4$ square, there cannot be more than four unmarked cells. Clearly, no row of the square can contain more than two unmarked cells. Take two rows of the square, whose numbers differ by 2. If one of the rows has two unmarked cells, then they are arranged in one of two ways: $\square \square \square$ or $\square$. Then, from the proven statement, it follows that all cells in the other row must be marked. Therefore, in the chosen pair of rows, there are no more than two unmarked cells, and the same applies to the remaining pair.

Since the $8 \times 8$ board can be divided into four $4 \times 4$ squares, there can be no more than 16 unmarked cells in it. Thus, at least 48 cells must be marked. An example with 48 marked cells is shown in the figure.

![](https://cdn.mathpix.com/cropped/2024_05_06_9304f7a3bc6f36cb1f9ag-36.jpg?height=302&width=300&top_left_y=1391&top_left_x=935)