1. On a $5 \times 7$ grid, 9 cells are marked. We will call a pair of cells with a common side interesting if exactly one cell in the pair is marked. What is the maximum number of interesting pairs that can be?
Answer: 35.

Solution. Let's call two cells adjacent if they share a side. The number of interesting pairs containing a given marked cell is no more than 4, and for a boundary cell, it is no more than 3. Then the total number of interesting pairs does not exceed $9 \cdot 4 = 36$. At the same time, if there are two adjacent marked cells, the interesting pair containing them is counted twice. Note that among the 9 cells in the $3 \times 5$ rectangle, there are necessarily two adjacent cells. Therefore, among the marked cells, there is either a boundary cell or two adjacent cells. Thus, the total number of interesting pairs does not exceed 35. An example of a marking with 35 interesting pairs is provided below.

![](https://cdn.mathpix.com/cropped/2024_05_06_627b343ad954e1e3a31bg-01.jpg?height=194&width=257&top_left_y=1054&top_left_x=908)