6. The bottom of the box is an $8 \times 8$ table. What is the smallest non-zero number of $2 \times 1$ or $1 \times 2$ tiles that can be placed on the bottom of the box so that no tile can be moved either horizontally or vertically? Each tile must occupy exactly two cells, not occupied by other tiles.
Answer: 28.

![](https://cdn.mathpix.com/cropped/2024_05_06_6a39912022b965b21feag-4.jpg?height=407&width=420&top_left_y=709&top_left_x=517)

Fig. 1: to the solution of problem 6.

Example: the arrangement of 28 tiles can be seen in Fig. 1.

Estimate. Cells not covered by tiles will be called empty. To begin with, let's prove that no two empty cells can be adjacent by side.

Assume the opposite: some two empty cells are adjacent. Consider the figure formed by the adjacent empty cells. Note that the figure cannot have concave angles (see the figure), because the tile covering the cell marked with a cross can be moved vertically if it is vertical, or horizontally if it is horizontal.

![](https://cdn.mathpix.com/cropped/2024_05_06_6a39912022b965b21feag-4.jpg?height=125&width=127&top_left_y=1714&top_left_x=744)

If the figure has no concave angles, then it is a rectangle. Let its dimensions be $a \times b$, where $a \geqslant b$. The situation $a \geqslant 3$ is impossible, because at least one side of the rectangle of length $a$ must be adjacent to tiles (not the edge of the box), but then the tile adjacent to a non-edge cell of the considered side can be pushed into the rectangle. A short enumeration can prove that rectangles $2 \times 2$ and $2 \times 1$ of empty cells are also impossible.

Thus, all empty cells are isolated. No empty cell can be at the edge of the board, otherwise one of the tiles adjacent to this empty cell can be pushed onto this empty cell. Tiles adjacent to an empty cell can be placed in only two ways, as shown in the figure.
![](https://cdn.mathpix.com/cropped/2024_05_06_6a39912022b965b21feag-5.jpg?height=182&width=420&top_left_y=673&top_left_x=596)

From this, in particular, it follows that two empty cells cannot be in the same row or column at a distance of two, and they also cannot be adjacent diagonally.

Now we are ready to complete the estimate. Suppose that it is possible to manage with fewer than 28 tiles. Then more than 8 empty cells will remain. Since empty cells cannot be adjacent to the edge of the box, they will be concentrated in the central $6 \times 6$ square. Divide the $6 \times 6$ square into four $3 \times 3$ squares. One of the squares must contain at least three empty cells. But a short enumeration of their potential placements shows that this is impossible. Contradiction.