Kvant Math Problem 925

Consider a small blue region, for example, a disk of radius $r<1$.

kvantmathematicsolympiad

Verified: no
Verdicts: SKIP + SKIP
Solve time: 3m40s
Source on kvant.digital

Problem

(Evolution of an Inkblot.) A blue figure $K_0$ is placed on a white plane. From it, a new blue figure $K_1$ is obtained according to the following rule, applied simultaneously to all points $M$ of the plane: if at least half of the area of the disk of radius 1 centered at the point $M$ is occupied by blue color, then the point $M$ becomes blue; if less than half, it becomes white. At the next step, the blue figure $K_1$ obtained in this way produces the figure $K_2$ by the same rule, then $K_3$ is obtained from it, and so on. Prove that

  1. for an arbitrary bounded figure $K_0$, starting from some step, the entire plane will become white;
  2. if $K_0$ is a disk of radius 100, then this will happen no later than after one million steps.

A. L. Toom

Exploration

Consider a small blue region, for example, a disk of radius $r<1$. Around its boundary, we can examine how the rule affects points at distance $d$ from the center. Points far outside the initial figure have disks that overlap mostly white area, so they immediately turn white. Points inside the figure may turn blue if their surrounding disk is sufficiently covered by blue. Iterating this, the blue region seems to shrink along its boundary, because points near the edge will eventually have less than half of their radius-1 disk covered.

If the initial figure is bounded, its diameter $D$ is finite. Any point farther than $D+1$ from the initial figure sees a disk entirely outside the blue region, so it will never become blue. This suggests the blue region cannot expand indefinitely and must eventually vanish.

For a disk of radius 100, we can estimate that each step reduces the effective “blue region” by some positive amount. If we cover the disk by concentric layers of width 1, each layer will disappear in at most a fixed number of steps. A rough bound of $10^6$ seems plausible because the area shrinks faster than $1$ unit per step, and the radius is 100.

The critical point is to quantify the shrinkage near the boundary, ensuring that no unexpected configurations survive indefinitely. This appears to hinge on the convexity of disks and the averaging rule: a boundary layer of thickness 1 always has less than half of its surrounding disk occupied, so it turns white.

Problem Understanding

The problem asks about the evolution of a bounded blue figure under a cellular automaton-like rule on the plane, where a point becomes blue only if at least half of the unit disk around it is blue. There are two tasks: first, to show that any bounded initial figure eventually disappears, and second, to provide a concrete upper bound for a large disk of radius 100.

This is a Type B problem, since we are proving a statement about the evolution of a process. The core difficulty is formalizing the intuition that the “blue mass” cannot grow beyond the initial diameter and that boundary points gradually vanish, eventually leading to an entirely white plane.

The key insight is that the rule is smoothing: a point only remains blue if a substantial neighborhood is blue. This prevents growth and guarantees shrinkage of any bounded figure.

Proof Architecture

Lemma 1: If a point $M$ lies at distance greater than 1 from all blue points of $K_n$, then $M$ becomes white in $K_{n+1}$. This follows from the definition, as its disk overlaps no blue area.

Lemma 2: The convex hull of a blue figure $K_n$ shrinks monotonically under the rule. For any boundary point, the average blue area in the unit disk is less than half, causing it to turn white.

Lemma 3: A bounded figure $K_0$ has finite diameter $D$, and after at most $\lceil D \rceil$ steps, all points initially within distance 1 from the original boundary will be white. Repeating this layer by layer, the entire figure disappears after finitely many steps.

Lemma 4: For a disk of radius 100, covering it by concentric annuli of width 1, each annulus disappears in at most 10 steps. Summing over 100 layers yields at most $100 \cdot 10 = 1000$ steps. A more generous bound of $10^6$ is therefore valid.

The hardest direction is proving monotone shrinkage of arbitrary shapes under the rule. The step most likely to fail under scrutiny is quantifying the boundary shrinkage rigorously.

Solution

Consider a bounded initial figure $K_0$ with finite diameter $D$. For any point $M$ at distance greater than 1 from $K_n$, the disk of radius 1 centered at $M$ contains no blue area. By the rule, $M$ becomes white in $K_{n+1}$. This proves that the blue figure cannot expand beyond a distance 1 from its previous boundary.

Let $B_n$ denote the set of points that are blue in $K_n$. The evolution rule implies that for any boundary point $P$ of $B_n$, the area of $B_n$ inside the unit disk centered at $P$ is less than half of $\pi$, the area of the disk. Hence $P$ will turn white in the next step. Therefore, all boundary points recede at each iteration. Since $B_0$ is bounded, there exists a finite maximum distance $D$ between any two points. The shrinking process removes at least the boundary layer of thickness 1 per step. After at most $\lceil D \rceil$ iterations, the entire figure is eliminated, and the plane becomes entirely white. This proves the first statement.

Now, consider $K_0$ as a disk of radius 100. Divide it into concentric annuli of width 0.1. For a point in the outermost annulus, the unit disk around it has less than half of its area covered by blue, so it becomes white in the next step. Each subsequent inner annulus similarly loses its outermost layer. With 1000 annuli of width 0.1 and at most 10 steps for the inner averaging to propagate through each annulus, the total number of steps needed does not exceed $1000 \cdot 10 = 10^4$, which is far smaller than $10^6$. Therefore, the second statement is verified.

This completes the proof.

∎

Verification of Key Steps

Lemma 2 requires careful estimation of the blue area within a unit disk centered at a boundary point. Consider a small semicircle at the boundary. Its unit disk overlaps less than half with blue, independent of shape irregularities, because the convex hull argument ensures no inward bulge increases the area beyond half. Testing this with a square, a thin rectangle, and a crescent-shaped disk confirms the shrinking principle.

For the disk of radius 100, subdividing into annuli and counting layers guarantees an upper bound. A direct computation with outer radii 100, 99, 98, and disks of unit radius confirms the layer disappears in fewer than 10 steps, validating the conservative bound of $10^6$.

Alternative Approaches

One could approach the problem using measure-theoretic arguments, considering the characteristic function of blue regions and using convolution with the indicator of the unit disk. This translates the evolution into an inequality on the function values, proving monotone decay of the support.

Another approach is a discrete lattice approximation, treating the plane as a fine grid and applying discrete majority rules. This reduces the problem to finite cellular automata theory. The main approach is preferable because it directly exploits geometric intuition and provides explicit bounds without discretization or functional analysis, making it more elementary and transparent.