Given an $8 \times 8$ board.

a) What is the minimum number of squares we need to mark on this board so that each of its $3 \times 3$ subboards has at least one marked square?

b) What is the minimum number of squares we need to mark on this board so that each of its $3 \times 3$ subboards has at least three marked squares?
Solution

a) Consider the figure below.

![](https://cdn.mathpix.com/cropped/2024_05_01_360f8ce7ec440aed2c7ag-25.jpg?height=420&width=434&top_left_y=2069&top_left_x=914)

Each of the four $3 \times 3$ sub-boards marked in the figure must have at least one cell marked. Additionally, with the four marked cells in the figure above, we have the desired property. Therefore, the minimum is 4.
b) Consider the figure below.

![](https://cdn.mathpix.com/cropped/2024_05_01_360f8ce7ec440aed2c7ag-26.jpg?height=409&width=411&top_left_y=361&top_left_x=728)

Notice that each of the six $3 \times 3$ pieces must have at least three cells marked. Also, there are two cells that can be counted for two pieces. With this, we will have a minimum of $6 \times 3 - 2 = 16$ marked cells. Observe also that with the 16 marked cells in the figure, we have the desired property.