Each cell of an $8 \times 8$ table can be colored white or black, such that each rectangle of size $2 \times 3$ or $3 \times 2$ contains two black cells that share a side. Determine the minimum number of black cells that can be on the table.
As usual in this kind of problem, we start by searching for upper (by exhibiting a configuration) and lower bounds (by double counting and/or tiling arguments) on the minimum number of black squares the board must contain.
For example, the configuration below (on the left) ensures that 28 black squares are sufficient; indeed, any vertical rectangle (of size $3 \times 2$) contains two squares on one of the rows 3 or 6, and any horizontal rectangle (of size $2 \times 3$) contains two squares on one of the columns 3 or 6. On the other hand, each of the 10 rectangles in the partial tiling below (on the right) must contain at least 2 black squares, so 20 black squares are necessary.
Unfortunately, these two bounds are not equal. We need to improve both of them until they are equal.
![](https://cdn.mathpix.com/cropped/2024_12_06_eaff4194f2fc53c944cag-4.jpg?height=666&width=652&top_left_y=1055&top_left_x=336)
![](https://cdn.mathpix.com/cropped/2024_12_06_eaff4194f2fc53c944cag-4.jpg?height=669&width=652&top_left_y=1050&top_left_x=1073)

By trial and error, we eventually find a new configuration that satisfies the conditions of the problem but contains only 24 black squares. It is the configuration below.
![](https://cdn.mathpix.com/cropped/2024_12_06_eaff4194f2fc53c944cag-4.jpg?height=675&width=664&top_left_y=1987&top_left_x=699)

On the other hand, using a simple tiling by rectangles seems a bit too brutal to indicate the best possible lower bound on the number of black squares needed. We study a given rectangle:
![](https://cdn.mathpix.com/cropped/2024_12_06_eaff4194f2fc53c944cag-5.jpg?height=249&width=292&top_left_y=361&top_left_x=888)

Here we observe that, among the 3 hatched squares, at least one must be a black square, otherwise our rectangle will never contain two adjacent black squares. In particular, the square in row 1, column 2 must have a black neighbor within this rectangle. Similarly, the square in row 2, column 2 must also have a black neighbor within our rectangle.
Armed with this observation, we focus on the minimum number of black neighbors that each square $c$ on the chessboard has:
$\triangleright$ if $c$ is one of the four corners, it could a priori have no black neighbors (which is indeed the case in our previous configuration);
$\triangleright$ if $c$ is one of the $2 \times 6=12$ squares on the top or bottom edge, it belongs to the central column of a horizontal rectangle, so it has at least one black neighbor;
$\triangleright$ similarly, if $c$ is one of the $2 \times 6=12$ squares on the left or right edge, it belongs to the central row of a vertical rectangle, so it has at least one black neighbor;
$\triangleright$ finally, if $c$ is one of the $6 \times 6=36$ squares in the center of the chessboard, it already has one black neighbor (say $d$); but then $c$ also belongs to the column (respectively, the row) of another horizontal (resp., vertical) rectangle that does not contain $d$, so $c$ has a second black neighbor.
In conclusion, we actually have at least $12+12+36 \times 2=96$ pairs $(c, d)$ of adjacent squares such that $d$ is a black square. Since each black square has at most four neighbors, it belongs to at most four such pairs. Therefore, we have at least $96 / 4=24$ black squares on our chessboard, which matches the upper bound found previously, and thus concludes the problem.