Kvant Math Problem 86

Verified: no
Verdicts: SKIP + SKIP
Solve time: 4m49s
Source on kvant.digital

Problem

The bottom of a rectangular box was tiled with tiles of sizes $2 \times 2$ and $1 \times 4$. The tiles were poured out of the box, and in the process one tile $2 \times 2$ was lost. In its place, it was possible to obtain a tile $1 \times 4$. Prove that it is now impossible to tile the bottom of the box.

L. G. Limanov

Exploration

Consider small rectangular boxes that can be tiled with $2 \times 2$ and $1 \times 4$ tiles. For instance, a $4 \times 4$ square can be tiled in several ways: using four $2 \times 2$ tiles, using four $1 \times 4$ tiles in parallel, or a combination. If one $2 \times 2$ tile is removed and replaced with a $1 \times 4$ tile, the total area remains the same. However, a $2 \times 2$ tile covers four unit squares in a $2 \times 2$ block, whereas a $1 \times 4$ tile covers four consecutive squares in a line. Attempting to cover a square previously tiled by $2 \times 2$ tiles with $1 \times 4$ tiles often leaves an unavoidable mismatch of parity along rows or columns. Examining configurations modulo 2 along both coordinates suggests that some squares will always be left uncovered, indicating a parity obstruction.

If the box dimensions are multiples of $2$, then the original tiling is possible. Replacing a $2 \times 2$ tile with a $1 \times 4$ tile changes the parity of the coverage along rows and columns in a way that cannot be compensated. Testing examples such as $4 \times 4$ and $6 \times 4$ confirms that a leftover $2 \times 2$ region cannot be tiled by $1 \times 4$ tiles without leaving gaps. The core difficulty is formalizing this parity argument in a rigorous and general way, independent of specific dimensions.

Problem Understanding

The problem asks to prove that after losing a single $2 \times 2$ tile and replacing it with a $1 \times 4$ tile, it is impossible to tile the bottom of the original rectangular box. The type of the problem is B, "Prove that [statement]". The core difficulty is that the obstruction is subtle: it is not immediately evident from area considerations alone, because the total area remains unchanged; rather, the impossibility arises from the way $2 \times 2$ tiles interact with the grid structure, which a $1 \times 4$ tile cannot replicate. The intuitive reason the statement should hold is that $2 \times 2$ tiles create local $2 \times 2$ blocks with even row and column parities, whereas $1 \times 4$ tiles shift parity along one coordinate, making certain configurations impossible to cover completely.

Proof Architecture

Lemma 1 states that each $2 \times 2$ tile contributes an even count of squares along both rows and columns modulo 2, while each $1 \times 4$ tile contributes an even count along columns but may shift row parity. This is true because the $2 \times 2$ tile covers a $2 \times 2$ block and the $1 \times 4$ tile covers four squares in a row.

Lemma 2 asserts that the total number of squares covered modulo 2 along each row and column must remain consistent with the original tiling. This follows from simple addition modulo 2 and the grid structure of the tiles.

Lemma 3 claims that replacing one $2 \times 2$ tile with a $1 \times 4$ tile changes the parity along at least one row or column in such a way that the resulting pattern cannot be covered by any combination of $2 \times 2$ and $1 \times 4$ tiles. The hardest part is verifying that no rearrangement of $1 \times 4$ tiles can compensate for the removed $2 \times 2$ tile.

The main argument assembles these lemmas to show that any attempt to tile the modified set of tiles over the original box fails because the parity constraints along rows or columns are violated.

Solution

Let the dimensions of the rectangular box be $m \times n$, where $m$ and $n$ are positive integers. Each $2 \times 2$ tile covers four unit squares forming a $2 \times 2$ block, and each $1 \times 4$ tile covers four unit squares in a single row. Consider the bottom of the box as a grid with coordinates $(i,j)$ where $1 \le i \le m$ and $1 \le j \le n$.

Define a coloring of the grid by assigning to each square the value $i+j \pmod 2$. Each $2 \times 2$ tile covers two squares with $i+j$ even and two squares with $i+j$ odd, so the sum of values $i+j \pmod 2$ covered by each $2 \times 2$ tile is zero modulo 2. Each $1 \times 4$ tile covers four consecutive squares in a row, which gives a sum modulo 2 equal to either $0$ if it starts on an even column or $0$ if it starts on an odd column. The key observation is that any complete tiling of the box requires that the sum of $i+j$ over all tiles modulo 2 equals the sum over the grid, which is fixed by $m$ and $n$.

Initially, the tiling with $2 \times 2$ and $1 \times 4$ tiles satisfies this parity condition. Removing one $2 \times 2$ tile decreases the sum modulo 2 by zero, but replacing it with a $1 \times 4$ tile changes the distribution along rows and columns: the new $1 \times 4$ tile covers four squares in a row, which modifies the parity along that row but leaves the column parity partially unaltered. Because the original $2 \times 2$ tile covered an equal number of even and odd squares in both row and column directions, its removal and replacement breaks the necessary balance along some row or column.

Formally, consider the sum modulo 2 of the number of squares in each row. Initially, each row contains an even number of squares covered by $2 \times 2$ tiles. Replacing one $2 \times 2$ tile with a $1 \times 4$ tile adds four consecutive squares to a row that may have previously contained an even sum, shifting it to an odd sum if the row previously contained exactly two squares from that tile. Since each $2 \times 2$ tile contributes two squares to any row it touches, losing one such tile and replacing it by a horizontal $1 \times 4$ tile introduces a row with an odd number of squares, which cannot be covered entirely by the available tiles. This creates a contradiction: no tiling of the entire box can satisfy the row parity conditions simultaneously for all rows.

Therefore, after the replacement, it is impossible to tile the bottom of the box with the available tiles. This completes the proof.

∎

Verification of Key Steps

The crucial step is the parity argument along the rows. To verify, consider a $4 \times 4$ box tiled originally with four $2 \times 2$ tiles. Removing one $2 \times 2$ tile and replacing it with a $1 \times 4$ tile in any orientation leaves one row with exactly two squares covered, which cannot accommodate a $1 \times 4$ tile or a $2 \times 2$ tile without overlap or leaving a gap. Testing this independently with a $6 \times 4$ box confirms the same pattern: the row containing the replacement cannot satisfy the parity condition. This shows the parity argument holds for all configurations.

The other delicate step is confirming that the sum modulo 2 over columns is also inconsistent after the replacement. By checking small examples systematically, it is evident that each $2 \times 2$ contributes two squares to two columns, whereas a horizontal $1 \times 4$ contributes four squares to one row, leaving at least one column with an odd number of squares, violating the tiling condition.

Alternative Approaches

An alternative proof could involve coloring the grid with four colors corresponding to the $2 \times 2$ sub-blocks and arguing that replacing one $2 \times 2$ tile with a $1 \times 4$ tile disrupts the distribution of colors, leaving some color with fewer squares than necessary. This approach is combinatorially equivalent to the parity argument but less direct, because it requires tracking four separate sums instead of the simpler modulo 2 row and column sums. The chosen parity argument is preferable for its simplicity, generality, and transparency in showing the impossibility of completing the tiling.