We build a tower from $2 \times 1$ dominoes in the following way. First, we arrange 55 dominoes to cover a $10 \times 11$ rectangle; this will be the first level of the tower. On top of this, we build further levels, each containing 55 dominoes, making sure that each level fits precisely on top of the previous one. The resulting structure is called stable if above every internal point of the $10 \times 11$ rectangle, which is different from the grid points, there is an internal point of a domino. How many levels does the lowest stable tower consist of?
Solution. Let's call the 10-unit long side of the rectangle covered by the tower horizontal, and the 11-unit long side vertical. The property of the tower described in the problem means that the $10 \times 11$ rectangle, when divided into $(1 \times 1)$ squares, has a domino in the tower that covers exactly any two adjacent squares. We call the pairs of squares adjacent along vertical edges horizontal pairs - there are 99 such pairs along the horizontal edges, and 100 pairs along the vertical edges.

First, we prove that a 5-level stable tower exists. It is clear that two levels are sufficient to cover all 100 vertical pairs of squares with dominos. For the 99 horizontal pairs, we use three additional levels. The horizontal side of the rectangle is even, so it can be tiled with dominos that cover only horizontal pairs. Let this be the third level. Leave out the rightmost and leftmost columns, as well as the top row of the rectangle! The resulting $8 \times 10$ table can be tiled with all horizontal dominos. This tiling can be extended to the left-out edge squares as well, let this be the fourth level. By now, we have taken care of all horizontal pairs except for the four "inner" pairs in the top row. On a fifth level, these can also be covered, for example, with a similar construction, if we now leave out the two outermost columns and the bottom row.

![](https://cdn.mathpix.com/cropped/2024_05_02_3e3be85169955788f3f7g-1.jpg?height=393&width=482&top_left_y=725&top_left_x=434)

![](https://cdn.mathpix.com/cropped/2024_05_02_3e3be85169955788f3f7g-1.jpg?height=238&width=244&top_left_y=735&top_left_x=930)

3rd level

![](https://cdn.mathpix.com/cropped/2024_05_02_3e3be85169955788f3f7g-1.jpg?height=236&width=241&top_left_y=733&top_left_x=1186)

4th level

![](https://cdn.mathpix.com/cropped/2024_05_02_3e3be85169955788f3f7g-1.jpg?height=235&width=241&top_left_y=739&top_left_x=1430)

5th level

covering vertical pairs

covering horizontal pairs

We claim that if a tower is at most 4 levels high, then it is not stable. This implies that the lowest stable tower is exactly 5 levels high. We prove this indirectly. First, note that if such a tower is stable, it must have at least 4 levels. Indeed: every non-edge square in the $10 \times 11$ rectangle has 4 neighbors, and the dominos covering these neighbors are placed on different levels. Therefore, if two adjacent squares are not both edge squares, then exactly one domino covers these two squares.

If a square $m$ has 3 edge neighbors (i.e., $m$ is on the edge of the rectangle but not a corner square), then there is an edge neighbor $m'$ such that exactly two dominos cover $m$ and $m'$ in the tower, and moreover, $m'$ is also an edge square. The other two edge neighbors of $m$ are covered by dominos that also cover $m$. Since any pair of edge-adjacent squares has either 3 or 4 edge neighbors, it follows from the above that there is no pair of adjacent squares that is covered by three dominos in the tower.

Now, let's examine the pairs of squares that are covered by exactly two dominos in the tower! According to the above, these pairs are disjoint, they can be located on the edge of the board, and each corner square forms a twice-covered pair with both of its neighbors. Traversing the 11 squares of the column ending in the bottom-left corner, we find that either there is a square in the column that is not part of a twice-covered pair (which is impossible), or the corner square at the other end of the column is not covered twice with its column neighbor, which we have also ruled out. This completes the proof, a 4-level stable tower indeed does not exist.