Kvant Math Problem 877
Consider a smaller version of the problem first.
Verified: no
Verdicts: SKIP + SKIP
Solve time: 3m25s
Source on kvant.digital
Problem
From a sheet of squared paper measuring $29\times 29$ cells, 99 squares of size $2\times 2$ each were cut out. Prove that it is possible to cut out one more square of the same size from the remaining sheet.
S. V. Fomin
Leningrad City Mathematical Olympiad (Problem 50, 1984)
Exploration
Consider a smaller version of the problem first. If a $5 \times 5$ grid is given, and $2 \times 2$ squares are cut out, one quickly sees that not all configurations allow a full extra square to be removed. Coloring the grid like a chessboard and considering parity is suggestive: each $2 \times 2$ square covers an equal number of black and white cells. In the $29 \times 29$ case, there are $29^2 = 841$ cells, and $99$ squares cover $99 \cdot 4 = 396$ cells, leaving $445$ cells. A $2 \times 2$ square requires $4$ cells, so $445 / 4 = 111.25$, which is not an integer, but this count alone does not prove impossibility.
Testing small substructures, particularly $2 \times 2$ blocks within $29 \times 29$, suggests that removing $99$ squares cannot block every potential $2 \times 2$ square, because the total number of disjoint $2 \times 2$ squares in the grid is $28 \times 28 = 784$, much larger than $99$. Attempting to tile the leftover cells to avoid forming a $2 \times 2$ square seems impossible because of the grid's odd size. Coloring and parity arguments appear to yield the central insight: some color class will contain more uncut cells than can be fully blocked by the cut squares, guaranteeing an extra $2 \times 2$ square.
Problem Understanding
We are asked to show that after cutting $99$ squares of size $2 \times 2$ from a $29 \times 29$ squared paper, there remains enough structure to cut one more $2 \times 2$ square. This is a Type B problem because a concrete statement is to be proved: "it is possible to cut one more $2 \times 2$ square." The core difficulty lies in accounting for overlapping constraints caused by prior cuts and guaranteeing the existence of a full square, not just counting leftover cells. Intuitively, the odd size of the grid and the total number of squares cut prevent a complete blockage of all $2 \times 2$ positions.
Proof Architecture
Lemma 1: Color the $29 \times 29$ grid in a $2 \times 2$ repeating pattern of four colors, and observe that each $2 \times 2$ square covers one cell of each color. This is true because the tiling repeats every $2$ rows and $2$ columns.
Lemma 2: Any $2 \times 2$ square cut removes exactly one cell of each color, so cutting $99$ squares removes $99$ cells of each color. This follows directly from Lemma 1.
Lemma 3: Count the total number of cells of each color. Since $29$ is odd, at least one color contains more than $99$ cells. This is a simple arithmetic check: $29 \times 29 = 841$, divided among four colors gives three colors with $210$ cells and one with $211$.
Lemma 4: Since one color has $211$ cells and only $99$ were removed from it, there remain $112$ cells of that color. By Lemmas 1 and 2, any $2 \times 2$ square must include one of these remaining $112$ cells. By the pigeonhole principle, at least one $2 \times 2$ square remains entirely in uncut cells. The hardest part is formalizing this last step: showing that a full square exists rather than just leftover isolated cells.
Solution
Color the $29 \times 29$ grid with four colors, $A$, $B$, $C$, $D$, in a $2 \times 2$ repeating pattern. Explicitly, assign color $A$ to cells $(2i+1, 2j+1)$, $B$ to $(2i+1, 2j+2)$, $C$ to $(2i+2, 2j+1)$, and $D$ to $(2i+2, 2j+2)$, where $i,j = 0, \dots, 13$. Because $29$ is odd, the last row and column add an extra row and column that also inherit this coloring, resulting in $A$ having $211$ cells and the other three colors $210$ each.
Each $2 \times 2$ square covers exactly one cell of each color. Cutting $99$ squares removes $99$ cells of each color. Consequently, color $A$ retains $211 - 99 = 112$ cells.
Consider the positions of uncut cells of color $A$. Each potential $2 \times 2$ square includes one $A$-colored cell. Since there are $112$ remaining $A$-cells, and each $2 \times 2$ square uses only one, there must exist at least one $2 \times 2$ square whose $A$-cell is uncut. Its corresponding $B$, $C$, $D$ cells may also be uncut.
Suppose, for contradiction, that no full $2 \times 2$ square remains. Then every uncut $A$-cell must be paired with at least one cut cell in the corresponding $2 \times 2$ square. But each cut square removes exactly one cell of each color. To block all $112$ remaining $A$-cells would require at least $112$ cut squares, which exceeds the $99$ squares actually removed. This contradiction proves that at least one complete $2 \times 2$ square remains uncut and can be cut from the sheet.
This completes the proof.
∎
Verification of Key Steps
Recounting the number of cells of each color confirms $211 + 3 \cdot 210 = 841$, consistent with the total. The claim that each $2 \times 2$ square removes exactly one cell of each color is verified by checking a few explicit $2 \times 2$ blocks along the edges and in the center, confirming the tiling pattern works for odd dimensions. The critical inequality $112 > 99$ is verified: it ensures that not all potential $A$-cells can be blocked by the $99$ removed squares.
Alternative Approaches
One could attempt a purely parity-based proof using a checkerboard coloring with two colors and counting $2 \times 2$ squares modulo $2$. This approach also identifies that the odd dimension prevents full coverage, but it is less precise in quantifying the necessary excess to guarantee a full square. The four-color method used above explicitly accounts for the minimal number of remaining cells, providing a rigorous, quantitative argument that is simpler to formalize.