1. For what smallest $k$ can $k$ cells be marked on a $9 \times 9$ board such that any placement of a three-cell corner piece will touch at least two marked cells?
Answer: 56.

Solution. It is not hard to notice that in any $2 \times 2$ square, at least three cells must be marked, and in each $1 \times 2$ rectangle, at least two cells must be marked. Since from a $9 \times 9$ board, 16 $2 \times 2$ squares and 8 $1 \times 2$ rectangles can be cut out, at least $16 \cdot 3 + 8 = 56$ cells must be marked in total. An example with 56 marked cells is shown in the figure.

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