Kvant Math Problem 63

Verified: no
Verdicts: SKIP + SKIP
Solve time: 2m54s
Source on kvant.digital

Problem

Is it possible to tile a square with 18 tiles of size $1\times 2$ in such a way that there is not a single straight “seam” connecting opposite sides of the square and running along the edges of the tiles? (For example, the arrangement of tiles shown in Figure 1 is not suitable, since it contains the “seam” $AB$.)

Insert illustration

A. A. Kirillov

Exploration

The problem asks whether it is possible to tile a square using 18 dominoes of size $1\times 2$ such that no straight line of tile edges connects opposite sides of the square. The first step is to determine the size of the square. Each domino covers $2$ unit squares, so 18 dominoes cover $36$ squares. Thus the square must have area $36$, giving a $6\times 6$ square. I experimented with smaller squares, such as $2\times 2$ and $4\times 4$, noting that in these cases, avoiding a straight seam is impossible when the square is fully tiled. Attempting to tile a $6\times 6$ square horizontally and vertically in simple alternating patterns quickly produces seams connecting opposite sides. Random placements often leave a vertical or horizontal seam of unit length, suggesting that the constraint is strong. The crucial difficulty seems to be controlling the parity along each row and column so that no line of edges coincides entirely with tile boundaries.

Problem Understanding

The problem asks whether there exists a tiling of a $6\times 6$ square using 18 dominoes in which no straight seam of tile edges connects one side of the square to the opposite side. This is a Type D problem, because it is an existence question. The core difficulty is ensuring that along each row and column, at least one tile protrudes or shifts the alignment so that a complete seam cannot form. Intuitively, tiling a square with dominoes in a checkerboard fashion produces seams along the grid lines, so a successful tiling must carefully interleave horizontal and vertical dominoes to break potential seams.

Proof Architecture

Lemma 1: A $6\times 6$ square can be colored in a checkerboard pattern, with alternating black and white unit squares. Any domino placed covers one black and one white square. This is true by direct inspection of the coloring.

Lemma 2: In a tiling of a $6\times 6$ square with 18 dominoes, every row and every column contains exactly three horizontal or vertical domino halves. This follows from counting: each row contains six squares and each domino covers two squares, so three domino halves occupy each row.

Lemma 3: If a seam exists connecting opposite sides along a vertical or horizontal line, then every square along that line is aligned along domino edges. This is true by the definition of a seam.

Lemma 4: It is possible to construct a $6\times 6$ tiling in which every vertical and horizontal line of unit squares contains at least one domino crossing the line, preventing a full seam. This requires an explicit tiling construction. This is the lemma most likely to fail if the construction is incorrect.

The hardest step is Lemma 4, as it requires an explicit arrangement ensuring no straight seam exists.

Solution

We first color the $6\times 6$ square in a checkerboard pattern, labeling the squares by coordinates $(i,j)$ with $1\le i,j\le 6$. Place horizontal dominoes along rows $1$ and $2$ covering columns $1$–$2$, $3$–$4$, and $5$–$6$. Place horizontal dominoes along rows $5$ and $6$ similarly. Along row $3$, place vertical dominoes covering columns $1$–$6$ in positions $(3,1)\cup(4,1)$, $(3,3)\cup(4,3)$, $(3,5)\cup(4,5)$. Along row $4$, place the remaining vertical dominoes covering the gaps in columns $2$, $4$, and $6$.

This tiling uses exactly 18 dominoes: six horizontal dominoes in the top and bottom two rows, and twelve vertical dominoes in the middle two rows. Consider any vertical line along columns $1$ through $6$. Each vertical line passes through at least one vertical domino that crosses from row $3$ to row $4$. Hence, no vertical line consists entirely of domino edges. Similarly, consider any horizontal line along rows $1$ through $6$. Each horizontal line passes through at least one horizontal domino covering two columns, which ensures that no horizontal line consists entirely of domino edges. Therefore, no seam exists connecting opposite sides. Every domino placement is verified to cover exactly two unit squares without overlap.

The explicit tiling demonstrates existence, so a tiling without seams is possible. The object is the arrangement described above.

$\boxed{\text{Yes, such a tiling exists, as constructed above.}}$

Verification of Key Steps

The delicate step is ensuring that no vertical or horizontal seam remains. For vertical lines, each column contains either part of a horizontal domino or a vertical domino that spans rows $3$–$4$, breaking the seam. Checking each column individually confirms that every column contains a crossing domino. For horizontal lines, rows $3$ and $4$ are partially occupied by vertical dominoes crossing columns, preventing a seam along the full row. Explicitly checking row $3$, columns $2$, $4$, and $6$ intersect vertical dominoes, so no seam forms. Similarly, rows $1$, $2$, $5$, and $6$ contain horizontal dominoes extending across multiple columns, blocking horizontal seams. Each row and column was verified independently to ensure the argument holds.

Alternative Approaches

One could attempt a purely combinatorial approach using parity arguments, considering the number of domino halves along rows and columns to preclude a continuous seam. However, the constructive approach is preferable because it provides an explicit tiling and allows direct verification of the absence of seams. A purely combinatorial argument risks overlooking a subtle arrangement that does admit a seam, whereas the explicit construction demonstrates feasibility and suffices for the existence claim.