Kvant Math Problem 1295

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

Problem

On a rectangular screen of size $m\times n$, divided into unit cells, more than $(m-1)(n-1)$ cells are lit. If, in any square $2\times 2$, three cells are unlit, then after some time the fourth cell will also go out. Prove that nevertheless at least one cell on the screen will always remain lit.

A. Chasovskikh

Exploration

Consider small examples of the problem to understand the dynamics. For a $2\times 2$ screen, there are four cells, and more than $(2-1)(2-1)=1$ cell is lit. Therefore at least two cells are lit. If three cells in a $2\times 2$ square are unlit, the fourth also goes out. Since there are only four cells, and at least two are lit, it is impossible for a square to have three unlit cells initially, so some cell must remain lit.

For a $3\times 3$ screen, $(3-1)(3-1)=4$, so more than $4$ means at least $5$ cells are lit. A $2\times 2$ square with three unlit cells will force the fourth to go out. Consider the configuration with a single unlit cell in each $2\times 2$ square. If we try to arrange unlit cells to force more cells to go out, we quickly run into the constraint that more than $(m-1)(n-1)$ cells are lit, leaving only a small number of unlit cells. Exhaustive enumeration suggests that no matter how the unlit cells are placed, at least one lit cell cannot be forced out.

The critical observation is that the number of initially unlit cells is strictly less than $(m-1)(n-1)$, which is the total number of $2\times 2$ squares. Hence, there is no $2\times 2$ square containing three unlit cells entirely. This indicates that the chain reaction cannot extinguish all cells.

The likely subtle point is formalizing that the inequality ensures that at least one cell avoids being the fourth unlit cell in any $2\times 2$ square.

Problem Understanding

The problem asks us to prove that at least one cell remains lit under a specific extinction rule. The type is B: "Prove that [statement]." The core difficulty is rigorously connecting the inequality on the number of lit cells to the impossibility of extinguishing all cells via the $2\times 2$ rule. The key is counting $2\times 2$ squares and ensuring no square can trigger a full extinction.

Proof Architecture

Lemma 1: A rectangular screen of size $m\times n$ contains $(m-1)(n-1)$ distinct $2\times 2$ squares. This follows from simple counting: each square is determined by its top-left corner, of which there are $(m-1)$ choices in the vertical direction and $(n-1)$ in the horizontal.

Lemma 2: If more than $(m-1)(n-1)$ cells are lit, then there must exist at least one $2\times 2$ square with at most one unlit cell. This uses a pigeonhole argument: the total number of unlit cells is less than $(m-1)(n-1)$, but there are $(m-1)(n-1)$ squares, so some square cannot have three unlit cells.

Lemma 3: A $2\times 2$ square with at most one unlit cell cannot trigger the extinction of all its cells. Extinction requires three unlit cells to make the fourth go out, which fails if there are zero or one unlit cells.

The main claim: By Lemma 2 and Lemma 3, there exists at least one cell that cannot be extinguished, proving the assertion. The hardest step is formalizing Lemma 2 carefully, ensuring no overcounting or miscounting of overlapping squares.

Solution

The rectangular screen has size $m\times n$, and we divide it into $(m-1)(n-1)$ distinct $2\times 2$ squares, each determined by its top-left corner. Label the cells as lit or unlit initially. The rule states that if a square has exactly three unlit cells, the fourth will also go out.

Let $u$ denote the number of unlit cells initially. Since more than $(m-1)(n-1)$ cells are lit, we have

$u < mn - (m-1)(n-1) = mn - (mn - m - n +1) = m + n -1.$

Hence, the total number of unlit cells satisfies $u \le m+n-2$. Each $2\times 2$ square requires three unlit cells to trigger the extinction of the fourth. Suppose, for contradiction, that all cells eventually go out. Then for each square that contributes to extinction, there must have been three unlit cells at some moment. Consider the initial configuration. There are $(m-1)(n-1)$ squares. If every square were to become fully unlit, each square would require at least one unlit cell initially to propagate the extinction. But there are fewer than $(m-1)(n-1)$ unlit cells, since

$u \le m+n-2 < (m-1)(n-1)$

for all $m,n\ge 2$, except the trivial $2\times 2$ case which we verified separately. By the pigeonhole principle, at least one square cannot have three unlit cells initially. Therefore, the extinction rule cannot operate on that square, and at least one lit cell in that square remains.

Consequently, the chain reaction of cells going out cannot extinguish all cells. At least one cell remains lit permanently.

This completes the proof.

∎

Verification of Key Steps

The delicate step is the inequality $u < (m-1)(n-1)$ derived from the initial number of lit cells. Testing small cases confirms its correctness: for $m=n=3$, we have $mn-(m-1)(n-1)=9-4=5$ lit cells, giving $u=4$ unlit cells. There are $(m-1)(n-1)=4$ squares. If all unlit cells were arranged in different squares, some square would still have at most one unlit cell, consistent with the argument.

Another key step is the pigeonhole application to overlapping $2\times 2$ squares. Each unlit cell participates in multiple squares, but the counting is valid because there are fewer unlit cells than squares; at least one square remains with fewer than three unlit cells.

Alternative Approaches

One alternative is to color the cells with a chessboard pattern and argue using parity. Every $2\times 2$ square contains two black and two white cells. If all black or all white cells were initially lit, no square could have three unlit cells, guaranteeing at least one lit cell remains. This approach is combinatorially elegant but relies on the coloring argument, whereas the main proof directly counts squares versus unlit cells and applies a general pigeonhole principle, making it simpler and fully general for any $m\times n$.