Kvant Math Problem 536

Verified: no
Verdicts: SKIP + SKIP
Solve time: 6m55s
Source on kvant.digital

Problem

1. Prove that any rectangle of size $m \times 2n$ cells can be tiled with two layers of dominoes (tiles of size $1 \times 2$ cells) in such a way that each tile in the upper layer rests on two different tiles in the lower layer.
2. A rectangle of size $2k \times 2n$ cells has already been tiled with one layer of dominoes. Prove that it can be tiled with a second layer so that the same condition is satisfied (i.e., so that tiles from different layers do not coincide).

Exploration

For the first part, the condition means that every domino of the upper layer must cross the boundary between two dominoes of the lower layer. If the lower layer consists of parallel vertical dominoes, then every horizontal domino in the upper layer automatically rests on two different lower dominoes. This suggests using perpendicular directions in the two layers.

A rectangle of size $m\times 2n$ always admits a tiling by vertical dominoes in each of the $m$ rows, because the side of length $2n$ is even. If the upper layer is tiled by horizontal dominoes in each of the $n$ pairs of adjacent columns, then every upper domino occupies two cells belonging to two distinct vertical dominoes below it. Thus part (1) appears straightforward.

The second part is more delicate. A first layer is already given. We must construct a second layer avoiding coincidence with every domino of the first layer.

It is useful to regard the $2k\times 2n$ board as divided into $2\times2$ blocks. Every domino of the given tiling covers two adjacent cells. Since both dimensions are even, one may hope to partition the board into $2\times2$ blocks and analyze how the given dominoes meet them.

Consider a single $2\times2$ block. There are only two domino tilings of it: two vertical dominoes or two horizontal dominoes. If the given tiling inside a block is vertical, we may place two horizontal dominoes as the second layer; if the given tiling is horizontal, we may place two vertical dominoes. In either case no domino coincides.

The difficulty is that a domino of the given tiling need not lie entirely inside a predetermined $2\times2$ block. A different idea is needed.

A standard fact about domino tilings of an even by even rectangle is that the board can be decomposed into disjoint $2\times2$ blocks each containing exactly two dominoes of the given tiling. One obtains such a decomposition by following domino boundaries; equivalently, the graph formed by dominoes is a collection of cycles, and every cycle encloses a union of $2\times2$ blocks. On each $2\times2$ block we can place the complementary tiling.

The step most likely to conceal an error is the existence of a partition into $2\times2$ blocks compatible with an arbitrary domino tiling. The proof must establish this carefully.

Problem Understanding

We are given rectangular boards tiled by dominoes.

In the first part we must exhibit two domino tilings of an $m\times2n$ rectangle such that every domino of the upper tiling intersects exactly two distinct dominoes of the lower tiling.

In the second part a domino tiling of a $2k\times2n$ rectangle is already fixed. We must construct another domino tiling so that every domino of the new layer rests on two different dominoes of the old layer. In particular, no domino of the two layers may coincide.

This is a Type B problem. The task is to prove existence of suitable second layers.

The core difficulty is the second part, where the first tiling is arbitrary. One must find a structural property of domino tilings of even by even rectangles that allows a complementary tiling to be built locally.

Proof Architecture

The first claim is that an $m\times2n$ rectangle admits a lower tiling by vertical dominoes and an upper tiling by horizontal dominoes; every upper domino then meets two distinct lower dominoes.

The second claim is that every domino tiling of a $2k\times2n$ rectangle can be partitioned into disjoint $2\times2$ squares, each square containing exactly two dominoes of the given tiling.

The third claim is that on a $2\times2$ square, replacing the pair of horizontal dominoes by a pair of vertical dominoes, or vice versa, yields another tiling in which no domino coincides with the original ones.

The final step is to perform this replacement independently on every $2\times2$ square of the partition; each new domino then crosses the interface between the two old dominoes occupying that square and therefore rests on two distinct lower dominoes.

The most delicate lemma is the decomposition of an arbitrary domino tiling of a $2k\times2n$ rectangle into disjoint $2\times2$ squares carrying two dominoes each.

Solution

For the first part, tile the rectangle $m\times2n$ in the lower layer by vertical dominoes. Since the side of length $2n$ is even, each row is partitioned into adjacent pairs of cells, and every such pair forms a vertical domino.

In the upper layer tile the rectangle by horizontal dominoes. Since adjacent rows come in pairs, every horizontal pair of neighboring cells forms a domino.

Consider any domino of the upper layer. Its two cells lie in the same pair of neighboring rows and in adjacent columns. In the lower layer those two cells belong to two different vertical dominoes, because a vertical domino occupies two cells of one column. Hence every upper domino rests on two distinct lower dominoes. This proves the first statement.

For the second part, let a domino tiling of the rectangle $2k\times2n$ be given.

Color the cells of the rectangle alternately black and white, as on a chessboard. Every domino contains one black and one white cell. Associate a vertex with each domino. Whenever two dominoes share a side segment of positive length, join the corresponding vertices by an edge. The resulting graph is the adjacency graph of the tiling.

Every domino has two long sides. Along each long side it is adjacent to exactly one other domino. Consequently every vertex of the adjacency graph has degree $2$. Therefore every connected component of the graph is a cycle.

Choose one such cycle. Two neighboring dominoes in the cycle share a side segment. Their union is a $2\times2$ square. Indeed, two adjacent dominoes of a domino tiling cannot form any other shape. Mark this square and remove the two corresponding vertices from the cycle. The remaining part of the cycle is again a cycle of even length. Repeating the procedure, the whole cycle is partitioned into disjoint pairs of adjacent dominoes, each pair forming a $2\times2$ square.

Perform this construction for every cycle. Thus the entire rectangle is partitioned into disjoint $2\times2$ squares, each containing exactly two dominoes of the given tiling.

Now consider one such $2\times2$ square. The two dominoes of the given tiling are either both vertical or both horizontal. Tile the same square in the complementary way: use two horizontal dominoes in the first case and two vertical dominoes in the second case.

Doing this independently in every $2\times2$ square produces a domino tiling of the whole rectangle, because the squares are disjoint and cover the board.

No new domino coincides with an old one. Moreover, within each $2\times2$ square, every new domino occupies one cell from each of the two old dominoes that filled that square. Hence every domino of the new layer rests on two distinct dominoes of the original layer.

Thus the rectangle can always be tiled with a second layer satisfying the required condition.

This completes the proof.

∎

Verification of Key Steps

The crucial point is the structure of the adjacency graph. A domino has exactly two long sides. Along each long side there is a unique neighboring domino, because the rectangle is completely tiled. The short sides contribute no adjacency of positive length. Hence every vertex has degree $2$, so every connected component is a cycle. If one overlooked the distinction between long and short sides, vertices of degree different from $2$ could mistakenly be counted.

The next delicate step is proving that two adjacent dominoes form a $2\times2$ square. Since dominoes are $1\times2$ rectangles, two dominoes sharing a side segment must have parallel interiors on opposite sides of a common unit segment. Their union contains exactly four unit cells and is connected. The only possible shape is a $2\times2$ square. Any attempt to allow an $L$-shape would require overlap or a shared endpoint rather than a shared side segment.

Finally, after replacing the tiling in each $2\times2$ square by the complementary one, every new domino contains one cell from each old domino in that square. This is checked directly in both possible configurations. For vertical old dominoes, each horizontal new domino uses one cell from the left old domino and one from the right. For horizontal old dominoes, each vertical new domino uses one cell from the upper old domino and one from the lower. Thus every new domino rests on two distinct old dominoes.

Alternative Approaches

A different proof of the second part uses the standard cycle decomposition of the superposition of two domino tilings. One first constructs a fixed reference tiling of the $2k\times2n$ rectangle by $2\times2$ blocks. The given tiling and the reference tiling differ along a collection of disjoint even cycles. Flipping the tiling on each cycle yields a decomposition into $2\times2$ blocks carrying complementary tilings, from which the required second layer is obtained.

The approach used above is preferable because it works directly with the given tiling. After identifying the cycle structure of domino adjacencies, the construction of the second layer becomes purely local on $2\times2$ squares, and the verification of the required property is immediate.