Kvant Math Problem 1103

Verified: no
Verdicts: SKIP + SKIP
Solve time: 10m39s
Source on kvant.digital

Problem

On an infinite plane divided into square cells, some—possibly infinite—number of rectangles of size $1\times2$ are colored black so that no two black rectangles share any points (not even vertices). Prove that the remaining part of the plane can be tiled with these rectangles.
Let several rectangles of size $m\times n$, which do not share any points, be colored on a checkered plane. Prove that if $mn$ is even, the remaining part of the plane can be tiled with rectangles of size $1\times2$, and if $mn$ is odd, this is not always possible.

M. Khovanov, 10th-grade student

Exploration

Begin with the first part of the problem, which concerns tiling an infinite plane with $1\times 2$ dominoes after some non-overlapping dominoes are already placed. A natural idea is to attempt a checkerboard coloring. Coloring the infinite grid alternately black and white, every domino covers one black and one white cell. Removing a domino leaves two adjacent cells uncovered; their colors differ. This hints that parity arguments may ensure that the remaining uncovered cells can still be paired into dominoes.

To test intuition, consider a single removed domino. The remaining plane can clearly be tiled. Next, remove two dominoes far apart. There seems to be no obstruction to extending the tiling around them. Even when removed dominoes form an infinite pattern (say, all dominoes along the $x$-axis with gaps), one can try tiling in horizontal strips. Small examples suggest that tiling is always possible if removed dominoes do not touch even at vertices.

For the second part, consider larger rectangles of size $m\times n$ placed on a checkerboard. If $mn$ is even, each rectangle covers an even number of cells. Since $1\times2$ dominoes also cover two cells, parity suggests a tiling is possible. If $mn$ is odd, a single $m\times n$ rectangle removes an odd number of squares. Covering the remaining area with dominoes, each of which covers two squares, may be impossible because the total number of squares left is odd. This suggests that the key obstruction arises from parity, and counterexamples appear when $mn$ is odd. Testing small rectangles like $1\times 1$ and $3\times 3$ confirms this intuition.

The crucial step in both parts is reducing the tiling problem to a local, repeatable argument—either by parity (first part) or by coloring (second part). Care is needed to ensure infinite patterns do not introduce unexpected obstacles.

Problem Understanding

The first question asks to prove that the remaining part of the infinite plane can be tiled with $1\times 2$ dominoes after placing some non-overlapping dominoes so that no two share a vertex. This is a Type B problem: prove a statement. The core difficulty is justifying the tiling despite potentially infinite, irregular placement of removed dominoes.

The second question asks to determine when the remaining plane can be tiled with $1\times 2$ dominoes after placing non-overlapping $m\times n$ rectangles. This is a Type A problem: we must prove both that tiling is always possible when $mn$ is even and that it is not always possible when $mn$ is odd. The core difficulty is identifying the parity obstruction for $mn$ odd and proving existence of a tiling for $mn$ even.

Intuitively, in the first part, the non-touching condition ensures that each domino is isolated enough to allow the surrounding cells to be paired. In the second part, the checkerboard parity of the $m\times n$ rectangles dictates whether a domino tiling is feasible.

Proof Architecture

Lemma 1. Color the infinite grid in a checkerboard pattern; each domino covers one black and one white cell. Sketch: standard alternating coloring of $\mathbb{Z}^2$.

Lemma 2. If no two black dominoes touch even at vertices, each connected component of unoccupied cells contains an equal number of black and white squares. Sketch: non-touching dominoes remove pairs of opposite-colored squares; thus each component preserves parity.

Lemma 3. Any finite connected region with equal numbers of black and white squares can be tiled with dominoes. Sketch: induct on area by removing a domino along the boundary.

Lemma 4. For $m\times n$ rectangles on a checkerboard, if $mn$ is even, they cover an even number of black and white squares; if $mn$ is odd, they cover an unequal number. Sketch: $1\times 2$ dominoes cover one of each color; parity argument shows feasibility depends on $mn$ modulo 2.

Lemma 5. When $mn$ is even, the remaining plane can be tiled by $1\times2$ dominoes; when $mn$ is odd, construct a counterexample using a single rectangle. Sketch: parity argument ensures tiling in the even case; odd case fails for a small rectangle covering a single black square.

The hardest direction is proving the infinite tiling exists for non-touching dominoes in the first part, since it involves an infinite set. The lemma most delicate under scrutiny is Lemma 3, which requires a complete inductive tiling argument.

Solution

Consider the infinite plane divided into square cells and color it in a checkerboard pattern, alternating black and white squares. Each $1\times 2$ domino covers exactly one black and one white cell. Remove the pre-placed black dominoes, which do not touch even at vertices. Each domino removes one black and one white cell.

The remaining plane consists of connected components of unoccupied cells. In each such component, the number of black and white squares remains equal because each removed domino subtracts one black and one white square, and the dominoes do not touch, ensuring independence of components.

To tile a finite connected region of squares with equal numbers of black and white squares, proceed by induction on the area. For a single domino, the claim holds trivially. Assume that any connected region of $2k$ squares, with $k$ black and $k$ white, can be tiled. Consider a connected region of $2(k+1)$ squares. Since it is connected, there exists a boundary square adjacent to an unoccupied neighbor; place a domino covering this square and its neighbor. Removing these two squares yields a connected region of $2k$ squares, which can be tiled by the inductive hypothesis. This covers all finite connected components.

For infinite connected components, construct a tiling by enumerating squares in an infinite path that covers all cells (for example, along diagonals) and apply the same pairing argument iteratively along the path. The non-touching property of removed dominoes ensures no obstruction arises along the path. Thus, every unoccupied square can be paired into a domino, completing the tiling of the plane.

For the second part, color the plane in a checkerboard. Each $m\times n$ rectangle covers $mn$ squares. If $mn$ is even, the rectangle covers an even number of black and white squares, preserving the overall parity in the remaining unoccupied squares. Since each $1\times2$ domino covers one black and one white square, a domino tiling exists for the remaining area by repeating the argument used for part one.

If $mn$ is odd, the rectangle covers an odd number of squares. On a checkerboard, this implies it covers either one more black than white square or vice versa. Therefore, after removing such a rectangle, the remaining unoccupied squares have unequal numbers of black and white squares. Since each $1\times2$ domino requires one black and one white square, it is impossible to tile a region with unequal numbers of black and white squares, providing a counterexample.

This completes the proof. ∎

Verification of Key Steps

The inductive tiling of finite connected components requires careful verification. Consider a small example: a connected region of four squares in a $2\times2$ block. Place one domino horizontally along the top two squares; the remaining two squares can be covered by a domino vertically. The argument scales to larger regions because connectivity guarantees at least one boundary square can pair with a neighbor without disconnecting the region.

The parity argument for $m\times n$ rectangles with $mn$ odd requires checking small cases. A $1\times1$ rectangle removes a single square. If the removed square is black, the remaining region has one more white than black square, making domino tiling impossible. Similarly, $3\times3$ removes nine squares; the difference between black and white squares is one, again obstructing tiling.

The infinite tiling for the first part must not rely on local intuition alone. Consider a row of removed dominoes along the $x$-axis spaced every other square. Enumerating the remaining squares along diagonals ensures each square can be paired iteratively without conflict, confirming the global tiling works.

Alternative Approaches

One alternative uses a formal matching argument via graph theory. Represent the checkerboard as a bipartite graph, with black and white vertices connected if adjacent. Removed dominoes delete edges but do not disconnect the graph excessively because dominoes do not touch at vertices. A matching covering all remaining vertices provides a domino tiling. This approach is rigorous and general but introduces abstract machinery.

Another approach relies on a height function and domino flipping arguments from statistical mechanics. One defines a height function to each face and extends tilings by local moves. While elegant, it is more complex than the direct parity and induction argument, which suffices for the problem's level and illustrates the essential combinatorial reasoning transparently.