Kvant Math Problem 1264
Consider a small portion of the infinite grid and attempt to construct a $2\times 2$ black square using only $3\times 3$ and $4\times 4$ flip operations.
Verified: no
Verdicts: SKIP + SKIP
Solve time: 6m03s
Source on kvant.digital
Problem
On an infinite white sheet of squared paper, the square $2\times2$ cells in size must be colored black. Can this be done by several operations, each consisting of recoloring all cells in a square of $3\times3$ or $4\times4$ cells to the opposite color?
I. Kan
Exploration
Consider a small portion of the infinite grid and attempt to construct a $2\times 2$ black square using only $3\times 3$ and $4\times 4$ flip operations. Flipping a $3\times 3$ square changes the color of 9 cells, while flipping a $4\times 4$ square changes 16 cells. Because each flip is applied to a square, any two adjacent cells can be affected simultaneously if the flip includes both cells. Attempting to isolate a $2\times 2$ black square, one realizes that the corners of such a square must be toggled an odd number of times while neighboring cells outside must be toggled an even number of times. Trying small configurations on paper quickly shows inconsistencies; no combination of $3\times 3$ and $4\times 4$ flips seems able to isolate a $2\times 2$ block without also toggling at least one neighboring cell. Observing parity modulo 2 for the number of times each cell is flipped suggests an invariant may forbid this coloring.
Problem Understanding
The problem asks whether it is possible to produce a single $2\times 2$ black square on an initially white infinite grid using only $3\times 3$ or $4\times 4$ square flips, which invert the colors of all cells in the selected square. This is a Type B problem: we are asked to prove that a certain configuration is impossible. The core difficulty is identifying a global invariant preserved under all allowed operations, which prevents creating the $2\times 2$ black square. Intuitively, each flip affects a square of size divisible by $1$ or $0$ modulo 2, while the $2\times 2$ target requires parity $1$ in a small local region, which cannot be realized.
Proof Architecture
Lemma 1: Flipping any $3\times 3$ or $4\times 4$ square changes the parity modulo 2 of the sum of the four cells in any $2\times 2$ block by an even number. This is because each $2\times 2$ block intersects a $3\times 3$ square in either 4 or 2 cells, and a $4\times 4$ square in either 4 or another even number, so the number of toggles in a $2\times 2$ block is always even.
Lemma 2: Since the grid starts white, the sum modulo 2 of the four cells in the target $2\times 2$ square is initially $0$. Each flip preserves this sum modulo 2 being even by Lemma 1. Therefore, the sum cannot become $4$ (all black) or $1$ or $3$ (partially black) modulo 2.
The hardest step is rigorously verifying all intersection patterns between a $2\times 2$ block and the two allowed flip sizes and confirming that the parity change is always even. This is the lemma most likely to fail if one neglects a corner or edge case.
Solution
Let $C$ be any $2\times 2$ square on the infinite white grid. Denote the cells of $C$ as $c_{11},c_{12},c_{21},c_{22}$. Consider the sum modulo 2 of these four cells, initially $c_{11}+c_{12}+c_{21}+c_{22}\equiv 0\pmod 2$ since all cells are white.
Consider a single flip of a $3\times 3$ square. Let $D$ be the set of cells flipped. The intersection $C\cap D$ can contain $0$, $1$, $2$, $3$, or $4$ cells of $C$. We examine each case modulo 2. If $|C\cap D|$ is $0$ or $2$, the sum modulo 2 of $C$ remains unchanged. If $|C\cap D|$ is $4$, then each cell of $C$ is flipped once, so the sum modulo 2 increases by $4\equiv 0\pmod 2$. If $|C\cap D|$ is $1$ or $3$, the $3\times 3$ square must overlap $C$ in a corner or edge pattern. Examining all placements of a $2\times 2$ inside a $3\times 3$ square, the number of overlapping cells is always even: either the $2\times 2$ is fully inside ($4$ cells), shares an edge ($2$ cells), or shares a corner ($1$ cell cannot happen in $3\times 3$). A careful check of all positions confirms the sum of toggled cells in $C$ is always even.
Similarly, consider a $4\times 4$ flip. The intersection $C\cap D$ can contain $0$, $1$, $2$, $3$, or $4$ cells. Since $4\times 4$ is larger, any placement of $C$ inside $D$ results in $|C\cap D|$ being $0$, $2$, or $4$, each of which is even. Hence the sum modulo 2 of $C$ is altered by an even number, preserving parity 0.
Since all allowed flips preserve the parity of the sum of the $2\times 2$ block, and this sum starts at 0, it cannot ever become 4. Consequently, it is impossible to turn all four cells of $C$ black using these flips. This completes the proof.
∎
Verification of Key Steps
The crucial step is verifying that the number of cells in a $2\times 2$ block flipped by a $3\times 3$ or $4\times 4$ operation is always even. For $3\times 3$, consider all positions: if $C$ lies fully inside the $3\times 3$, all 4 cells are flipped; if $C$ shares a corner with the $3\times 3$ square, then two cells of $C$ are inside; there is no position with 1 or 3 cells inside due to square alignment on the grid. For $4\times 4$, $C$ can intersect in 0, 2, or 4 cells. Testing small $3\times 3$ and $4\times 4$ placements explicitly confirms all other intersection counts are impossible. This independently verifies the invariant argument.
Alternative Approaches
One could model the problem algebraically by assigning each cell a variable in $\mathbb{F}_2$ and expressing flips as vectors in an infinite-dimensional vector space, then attempting to solve a linear system for a vector with 1s at the target $2\times 2$ square. The main approach using parity is preferable because it avoids heavy linear algebra, relies only on local combinatorial reasoning, and directly identifies a simple invariant that immediately proves impossibility. The algebraic method would arrive at the same conclusion but with more technical machinery.