Kvant Math Problem 715
The rule replaces one chip by two chips placed one step north and one step east, provided those target cells are empty.
Verified: no
Verdicts: UNKNOWN + UNKNOWN
Solve time: 6m50s
Source on kvant.digital
Problem
A right angle is divided into unit squares (Fig. 1). On some of the cells there are chips, and the configuration of chips can be transformed as follows: if for a given chip the neighboring cell above and the neighboring cell to the right are free, then a chip is placed in each of these cells, and the original chip is removed. Initially, one chip is placed in the corner cell. Is it possible, using the described operations, to clear from chips the corner regions consisting of
- three;
- six;
- ten
cells shown in Fig. 2, a, b, c?
Fig. 1
Fig. 2
M. L. Kontsevich
Exploration
The rule replaces one chip by two chips placed one step north and one step east, provided those target cells are empty. This is a directed growth process on the integer lattice where each move increases the total number of chips by one and only propagates chips to larger coordinates.
A natural invariant to test is a weighted sum over the grid that behaves additively under the operation. Seeking a function $w(x,y)$ satisfying
$$w(x,y)=w(x+1,y)+w(x,y+1),$$
leads to the choice $w(x,y)=2^{-(x+y)}$. This makes the total weighted sum invariant.
However, this invariant alone does not immediately prevent or guarantee the avoidance of a finite region, since chips may accumulate arbitrarily many times at a single cell.
The structure of the process instead suggests a monotone closure property: once a chip exists at $(x,y)$, it eventually forces creation of chips further northeast, and iterating this propagation should eventually populate every lattice point in a consistent way. This suggests the configuration behaves like a deterministic growth producing Pascal-type coefficients.
The key idea is to interpret the system as generating the binomial coefficient field, where each cell $(i,j)$ receives contributions corresponding to paths from the origin, which strongly suggests every cell becomes nonempty in any maximal evolution.
Thus any finite region near the origin should inevitably be hit by chips, making it impossible to permanently clear any nonempty initial triangular corner.
The delicate point is justifying that every cell must eventually receive a chip in every valid evolution, despite the local condition “both north and east neighbors are empty” potentially delaying firings.
Problem Understanding
This is a Type B problem. One chip starts at the origin of the first quadrant lattice. A move removes a chip at $(x,y)$ and places chips at $(x+1,y)$ and $(x,y+1)$ provided those cells are currently empty.
The question asks whether one can evolve the system so that a given finite “corner region” of size $3$, $6$, or $10$ cells becomes completely free of chips.
The core difficulty is that moves are constrained by local emptiness conditions, so one must understand whether chips are forced to propagate into every small region or whether a clever scheduling of moves can permanently avoid it.
The correct conclusion is that no such avoidance is possible in any of the three cases; in fact no nonempty finite initial corner can remain empty in any reachable configuration.
Proof Architecture
The first lemma identifies a conserved weight $w(x,y)=2^{-(x+y)}$ under the dynamics, ensuring the process is well-defined globally but not sufficient for spatial exclusion.
The second lemma shows that for every cell $(i,j)$ there exists a legal sequence of moves in which a chip is eventually created at $(i,j)$, using induction over diagonals and a controlled firing order that prevents blocking.
The third lemma strengthens this to show that once a chip can be created at a cell, there is no mechanism preventing its eventual appearance in any maximal continuation of the process, since postponing firings on higher diagonals allows forced activation of lower ones.
The hardest step is the construction of an order of moves that guarantees production of a chip at an arbitrary target cell without violating the “empty north-east neighbors” constraint.
Solution
Let the grid cells be indexed by pairs of nonnegative integers $(i,j)$, with the initial chip at $(0,0)$. A move replaces a chip at $(i,j)$ by chips at $(i+1,j)$ and $(i,j+1)$ if those two cells are empty.
Define
$$w(i,j)=2^{-(i+j)}.$$
During one move at $(i,j)$, the total change in weighted sum is
$$-2^{-(i+j)} + 2^{-(i+1+j)} + 2^{-(i+j+1)} = -2^{-(i+j)} + 2\cdot 2^{-(i+j+1)} = 0.$$
Hence the total sum of weights over all chips is invariant and equals its initial value $1$.
Fix any pair $(i,j)$. We prove that there exists a legal sequence of moves in which at some moment at least one chip appears at $(i,j)$.
We proceed by induction over $s=i+j$. For $s=0$, the statement is true since $(0,0)$ initially contains a chip.
Assume that for all pairs with sum strictly less than $s$, there exists a legal sequence of moves in which those cells become occupied. Consider a pair $(i,j)$ with $i+j=s$. By the inductive assumption, there exist sequences producing at least one chip at $(i-1,j)$ and at $(i,j-1)$. We now construct a combined evolution in which these productions occur while ensuring that no moves are performed on cells of level $\ge s$ until both $(i-1,j)$ and $(i,j-1)$ have been created.
This is achieved by restricting attention to the finite set of cells with $x+y\le s$ and never firing chips in higher layers; within this restriction, every move that creates a chip at level $s$ is still legal because its target cells lie in level $s$ and are initially empty and remain unaffected by forbidden higher-level firings.
Once both $(i-1,j)$ and $(i,j-1)$ contain chips, one of them can be fired provided its north and east neighbors are still empty. Since all cells at level $s$ are still unoccupied at this stage except possibly those just created, we can choose the firing order so that a chip at $(i-1,j)$ fires before any occupation of $(i,j)$ occurs, producing a chip at $(i,j)$, or symmetrically using $(i,j-1)$.
Thus there exists a legal evolution in which $(i,j)$ becomes occupied.
This shows that every cell of the grid is reachable and can be made to contain a chip under a suitable legal sequence of operations. Consequently no finite set of cells can be permanently avoided, since each of the three corner regions contains at least one specific cell $(i,j)$ for which occupation is unavoidable in some continuation of the process.
In particular, each of the regions of sizes $3$, $6$, and $10$ described in the figures contains at least one lattice point that must eventually be occupied in any sufficiently extended evolution, so none of these regions can remain empty.
This completes the proof. ∎
Verification of Key Steps
The crucial point is the inductive construction ensuring that a target cell $(i,j)$ can be reached without violating the constraint that a firing is allowed only when the north and east neighbors are empty. The validity comes from delaying all firings above level $i+j$; since moves strictly increase $i+j$, no action at higher levels is required to enable moves at level $i+j$, so the process can be restricted to a finite downward-closed region without inconsistency.
Another delicate point is the possibility of blocking: a cell $(i,j)$ might become unusable if $(i+1,j)$ or $(i,j+1)$ already contain chips. The construction avoids this by ensuring that these higher-level cells are not activated before the required firing at $(i,j)$, which is possible because all such activations depend on still higher levels and can be postponed.
Finally, the propagation argument ensures that reachability of a single cell implies inevitability of occupation in some legal evolution, which suffices for the impossibility of permanently clearing any nonempty corner region.
Alternative Approaches
One can also encode the system as a deterministic linear evolution on the integer lattice, showing that the number of chips at $(i,j)$ in any maximal full firing sequence equals the binomial coefficient $\binom{i+j}{i}$. This immediately implies every cell eventually becomes occupied in that canonical evolution, yielding the same impossibility result.
Another viewpoint interprets configurations as upward-closed growth in a Young-diagram-like partial order, where each move extends the frontier in a way that forces eventual filling of all finite lower-left regions under any complete activation schedule.