Placing dominoes on a chessboard

Question

Find the smallest number of dominoes we must place on an $8×8$ chessboard, so that in every $2×2$ square, at least one of the squares is covered by a domino. I am getting confused again and again as I am making many cases and they seem to make the problem harder. Either this problem very easy or very hard.

Answer 1

There are 49 $2\times 2$ boards.

A single domino can cover 6 $2\times 2$ boards.

Thus you need at least 9 dominoes.

On the other hand we can cover your squares claim with 11 dominoes using a greedy type algorithm. I can deploy a maximum of 6 dominoes that cover 6 $2\times 2$ squares per domino. Place dominoes at $(B7,C7)$, $(E7,F7)$, $(B5,C5)$, $(E5,F5)$, $(B3,C3)$, and $(E3,F3)$. The remaining $2\times 2$ all lie along the perimeter of the board and I can deploy 4 dominoes that cover 12 more $2\times 2$ squares. Place dominoes at $(B1,C1)$, $(E1,F1)$, $(H7,H6)$, and $(H4,H3)$. Leaving the final square to be covered with a domino at $(H1,H2)$.

UPDATE: In order to use 9 dominoes, 8 of the dominoes would have to be placed so that they could each cover 6 $2\times 2$ squares, with no overlap. This is impossible. Thus the minimum is at least 10 and I have found a way to do that, but the trick is to allow multiple dominoes cover some squares previously covered by other dominoes.

Answer 2

$10$ dominoes:

$$\begin{array}{|c|c|c|} \hline \;\;&&&&5&&8&\\ \hline &1&1&&5&&8&\\ \hline &&&&&&&\\ \hline &2&&4&&7&&10\\ \hline &2&&4&&7&&10\\ \hline &&&&&&&\\ \hline &3&3&&6&&9&\\ \hline &&&&6&&9&\\ \hline \end{array}$$

I placed dominoes $1$ and $3$ for maximal coverage. It’s wasteful to have parallel dominoes with two spaces between them, so I tried turning dominoes $2$ and $4$ the other way. At that point the rest more less just fell into place.

Alternatively, dominoes $5$ and $6$ could be turned horizontal in the second and seventh rows and dominoes $8$ and $9$ moved over to the last column:

$$\begin{array}{|c|c|c|} \hline \;\;&&&&&&\;\;&8\\ \hline &1&1&&5&5&&8\\ \hline &&&&&&&\\ \hline &2&&4&&7&&10\\ \hline &2&&4&&7&&10\\ \hline &&&&&&&\\ \hline &3&3&&6&6&&9\\ \hline &&&&&&&9\\ \hline \end{array}$$