Problem 9.6. A white checkered $8 \times 8$ table is given. In it, 20 cells are painted black. What is the minimum number of pairs of adjacent white cells that could remain?
Answer: 34.

Solution. We will call a pair of cells that are adjacent by side simply a pair. Let's first count the total number of pairs. There are 7 pairs in each row and column, so there are a total of $7 \cdot 8 \cdot 2 = 112$ pairs.

We will call cells that touch the border of the table boundary cells, and those that do not touch the border middle cells. Among the 20 black cells, consider the maximum number of middle black cells, no two of which are adjacent by side. We will call these black cells main, and let there be $s$ of them. Since all the middle cells of the table can be divided into $\frac{6^2}{2} = 18$ non-overlapping pairs (dominoes $1 \times 2$), in each of which there is no more than one main black cell, then $s \leqslant 18$.

In the initially white table, we will color the cells black one by one until there are 20, starting with $s$ main black cells. We will say that a black cell ruins a pair of adjacent cells if it is in it. Each of the main black cells ruins 4 pairs, so in total they ruin $4s$ pairs. Next, we color in black, in any order, the middle non-main cells (which are already contained in at least one ruined pair) and the boundary cells (which in principle are contained in three or two pairs). The remaining $20-s$ black cells ruin no more than 3 pairs each, so in total they ruin no more than $3(20-s) = 60 - 3s$ new pairs. In total, no more than $4s + 60 - 3s = 60 + s \leqslant 60 + 18 = 78$ pairs are ruined. Then, the number of unruined pairs, consisting only of white cells, is no less than $112 - 78 = 34$.

An example with 34 pairs of white cells is constructed as follows: consider 18 main black cells and 2 more boundary cells, each of which does not form a pair with other black cells (Fig. 3).

|  |  |  |  |  |  |  |  |
| :--- | :--- | :--- | :--- | :--- | :--- | :--- | :--- |
|  |  |  |  |  |  |  |  |
|  |  |  |  |  |  |  |  |
|  |  |  |  |  |  |  |  |
|  |  |  |  |  |  |  |  |
|  |  |  |  |  |  |  |  |
|  |  |  |  |  |  |  |  |
|  |  |  |  |  |  |  |  |

Fig. 3: to the solution of problem 9.6