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

Solution. Let's note a few simple facts at the beginning.

1) In any $2 \times 3$ rectangle, there is no more than one unmarked cell. This is verified by direct enumeration.
2) In any $3 \times 3$ square, there are no more than two unmarked cells, and if there are two, they are located in opposite corners of the square. Otherwise, there will be two unmarked cells that fall into one $2 \times 3$ rectangle.
3) Any $3 \times 6$ rectangle (vertical or horizontal) contains no more than three unmarked cells. Indeed, divide the rectangle into two $3 \times 3$ squares and cover their common side with a $2 \times 3$ rectangle. By 1), there can be only one unmarked cell in it. Then, in one of the squares, two adjacent corner cells are marked. By 2), there is no more than one unmarked cell in this square, and no more than two in the other.

Divide the board into 9 $3 \times 3$ squares. By 3), no more than five of them can contain two unmarked cells. If there are 4 such squares, the total number of unmarked cells does not exceed $4 \cdot 2 + 5 = 13$. If there are five, then according to 3), they must be arranged in a checkerboard pattern. Therefore, the unmarked cells can only be arranged as shown in the figure (up to a rotation of the board).

![](https://cdn.mathpix.com/cropped/2024_05_06_9304f7a3bc6f36cb1f9ag-32.jpg?height=329&width=340&top_left_y=1212&top_left_x=915)

But then, in the remaining squares, all cells must be marked, since any of them can be covered by a $2 \times 3$ rectangle together with some unmarked cell. This means that in this case, there can be no more than 10 unmarked cells. An example with 13 unmarked (i.e., 68 marked) cells is shown in the figure.

![](https://cdn.mathpix.com/cropped/2024_05_06_9304f7a3bc6f36cb1f9ag-32.jpg?height=328&width=340&top_left_y=1732&top_left_x=915)