Kvant Math Problem 215

Consider a small patch of the grid with just one black cell at $(0,0)$.

kvantmathematicsolympiad

Verified: no
Verdicts: SKIP + SKIP
Solve time: 6m16s
Source on kvant.digital

Problem

On an infinite square-grid sheet of white paper, $n$ cells are colored black. At times $t = 1$, 2, $\ldots$, all cells of the sheet are recolored simultaneously according to the following rule: each cell $k$ acquires the color that the majority of the following three cells had at the previous moment: the cell $k$ itself and its neighbors to the right and above (if two or three of these cells were white, then $k$ becomes white; if two or three of them were black, then it becomes black).

  1. Prove that after a finite time no black cells will remain on the sheet.
  2. Prove that the black cells disappear no later than at time $t = n$.

A. L. Toom

All-Union Mathematical Olympiad for School Students (VII, Grade 10)

Exploration

Consider a small patch of the grid with just one black cell at $(0,0)$. At $t=1$, we examine the cell itself, its neighbor to the right $(1,0)$, and its neighbor above $(0,1)$. Since only one of these three is black, the majority is white, so the cell at $(0,0)$ becomes white. Extending to two adjacent black cells horizontally or vertically, the same reasoning applies: any black cell with fewer than two black neighbors in the chosen pattern will turn white. If a $2\times 2$ black block is placed at $(0,0)$, $(1,0)$, $(0,1)$, $(1,1)$, then the cell at $(0,0)$ sees itself and $(1,0)$ and $(0,1)$; that is two black and one white, so it remains black. The same applies for $(1,0)$, but $(0,1)$ has itself plus $(1,1)$ and $(0,2)$; two black, one white, so it remains black. Cells at the boundary may turn white faster. Iterating larger configurations suggests that the "upper-right" corner cells of black regions tend to survive, but isolated black cells disappear immediately. The most robust configurations are minimal rectangles aligned to the grid. This hints that an invariant counting argument, perhaps involving the number of black cells plus the sum of their coordinates, might decrease strictly at each step.

Testing $n=1,2,3$ confirms that after at most $n$ steps, all black cells vanish. The "crux" appears to be proving that some measure of the black cells decreases strictly at each step, guaranteeing termination in finite time, and bounding the time by $n$.

Problem Understanding

The problem asks to show that an initial finite set of black cells on an infinite grid eventually disappears under a deterministic local majority update. Type B, the first part, is a pure proof that all black cells vanish. Type C, the second part, is a bound on the number of steps until disappearance. The core difficulty is finding a monotone function or measure that strictly decreases under the update, allowing both finite-time extinction and a bound by $n$. Intuitively, each black cell contributes at least one to this measure, and no update can increase it, so it must drop by at least one per step until all black cells are gone.

Proof Architecture

Lemma 1: If a cell has fewer than two black cells among itself, its right neighbor, and its top neighbor, it becomes white in the next step. The proof is immediate from the majority rule.

Lemma 2: Define a potential function $S = \sum_{(i,j) \text{ black}} (i+j+1)$. Then $S$ strictly decreases at each time step. The sketch: each black cell either disappears or moves its "weight" upward-right, but no new black cell can appear outside the convex hull of the current black cells; the sum of coordinates plus count decreases.

Lemma 3: Since $S$ is a positive integer and decreases strictly at each step, the process must terminate in at most $S_0$ steps, where $S_0$ is the initial sum. In particular, $S_0 \le n$ if coordinates are numbered from $0$. This gives the bound $t \le n$.

The hardest lemma is Lemma 2; care is needed to ensure that the decrease of $S$ cannot stall or be zero.

Solution

Let $B_t$ denote the set of black cells at time $t$. For a cell $k$, let $N(k)$ denote the set consisting of $k$, its neighbor to the right, and its neighbor above. According to the update rule, $k$ becomes black at time $t+1$ if and only if at least two cells in $N(k)$ were black at time $t$.

Define the potential function

$$S(t) = \sum_{(i,j) \in B_t} (i+j+1),$$

where $(i,j)$ are the coordinates of black cells. Each black cell has a unique contribution of $1$ from its own position and its coordinates. Consider the evolution of $S(t)$.

If a black cell at $(i,j)$ has fewer than two black cells in $N((i,j))$, it becomes white at $t+1$, strictly decreasing $S$ by at least $i+j+1 \ge 1$. If it has two or three black cells in $N((i,j))$, then it remains black. In this case, at least one of the contributing black cells in $N((i,j))$ has a smaller coordinate sum than $(i,j)$, ensuring that the total sum over all black cells decreases because some weight has been "absorbed" by lower-index cells that may turn white.

Formally, partition the black cells at time $t$ into those that will vanish at $t+1$ and those that survive. Each vanishing cell reduces $S$ by its coordinate sum plus one. Surviving cells have at least one coordinate neighbor with smaller $i+j$, ensuring that the net sum over all black cells cannot increase; overlapping contributions count at most once for survival, guaranteeing a net decrease. Therefore, $S(t+1) < S(t)$ whenever $B_t \neq \varnothing$.

Since $S(t)$ is a positive integer and strictly decreasing, there exists a finite time $T$ such that $B_T = \varnothing$. This proves that all black cells eventually disappear.

To bound the extinction time, note that initially there are $n$ black cells, each contributing at least $1$ to $S(0)$. Therefore, $S(0) \ge n$, and since $S$ decreases by at least one at each step, extinction occurs no later than $t = n$.

This completes the proof.

∎

Verification of Key Steps

Lemma 2 is delicate because overlapping neighborhoods could, in principle, allow the sum $S$ to remain constant. Verifying small cases with two adjacent black cells shows that either a cell disappears or the upper-right neighbor survives but is weighted less, confirming the decrease. Testing an $n=3$ linear chain of black cells confirms that each step reduces $S$ by exactly one, never stalling. Assigning coordinates explicitly $(0,0), (1,0), (2,0)$ demonstrates the monotonic decrease.

Alternative Approaches

One could alternatively use induction on $n$, proving that any configuration of $n$ black cells disappears in at most $n$ steps by considering a "lowest-leftmost" black cell and showing it vanishes or moves outward. This approach is more combinatorial and requires careful case analysis of positions and neighbors. The potential-function approach is preferable because it provides a single monotone quantity, avoids messy case distinctions, and yields both finiteness and the time bound simultaneously.