3. What is the minimum number of cells on a $3 \times 2016$ board that can be painted so that each cell has a side-adjacent painted cell?

(A. Khryabrov)
Answer: 2016.

Solution: Let's divide our board as follows:

![](https://cdn.mathpix.com/cropped/2024_05_06_9da091ab250974b7674ag-2.jpg?height=252&width=1196&top_left_y=2147&top_left_x=493)

We have obtained two three-cell corners and 1007 D-hexomino figures. In our three-cell corners, at least one cell must be shaded (either the corner cell or a cell adjacent to the corner). We will prove that in each D-hexomino of the partition, at least two cells will be shaded. Let's number the cells of an arbitrary D-hexomino as follows:

![](https://cdn.mathpix.com/cropped/2024_05_06_9da091ab250974b7674ag-3.jpg?height=177&width=352&top_left_y=654&top_left_x=909)

If one of the cells 2 or 3 is shaded, then the adjacent cell belonging to the D-hexomino will also be shaded. If neither 2 nor 3 are shaded, then 1 or 5 (as a neighbor of cell 2) and 6 or 4 (as a neighbor of cell 3) must be shaded. In any case, our D-hexomino will have at least two shaded cells.

In the end, we get an estimate for the number of shaded cells, which is at least \(1007 \cdot 2 + 2 = 2016\).

Now let's provide an example where this estimate is achieved:

![](https://cdn.mathpix.com/cropped/2024_05_06_9da091ab250974b7674ag-3.jpg?height=408&width=1382&top_left_y=1675&top_left_x=403)

We shade 2016 cells, located on the second horizontal row.