1. Pete and Vasya are playing the following game. Pete marks $k$ cells on a $13 \times 13$ board, after which Vasya places a $1 \times 6$ rectangle on the board and tells Pete which of the marked cells are covered by the rectangle (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: 84.

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

![](https://cdn.mathpix.com/cropped/2024_05_06_9304f7a3bc6f36cb1f9ag-28.jpg?height=468&width=477&top_left_y=948&top_left_x=847)