Kvant Math Problem 1093

Represent the configuration by numbers $a_1,\dots,a_n\in{0,1,2}$ arranged cyclically.

kvantmathematicsolympiad

Verified: no
Verdicts: SKIP + SKIP
Solve time: 8m08s
Source on kvant.digital

Problem

Numbers 0, 1, and 2 are placed at $n$ points on a circle. Then the following transformation is performed simultaneously at all points: each number 2 is replaced by 0, and then 1 is added to the number at the next point clockwise. Suppose that initially the number of twos was equal to $k\ge 1$.

  1. After how many transformations is it guaranteed that no twos will remain?
  2. Suppose, in addition, that at the remaining $n-k$ points there were initially ones. Prove that eventually there will remain $k$ ones and $n-k$ zeros (Fig. 1).

Figure 1

N. Alexandru (Romania)

Exploration

Represent the configuration by numbers $a_1,\dots,a_n\in{0,1,2}$ arranged cyclically. Let $T$ denote one transformation.

If a point contains $0$ or $1$, its value is unchanged, except that it may receive $1$ from the previous point if that point contained $2$. If a point contains $2$, it becomes $0$ and contributes $1$ to the next point. Hence, if $b_i$ is the indicator of the event $a_i=2$, then

$$(Ta)i=a_i-2b_i+b{i-1},$$

indices being taken modulo $n$.

The first question asks for a guaranteed time after which no $2$ can occur. A natural quantity to inspect is the total sum

$$S=\sum_{i=1}^n a_i.$$

Under one transformation,

$$S'=\sum_i(a_i-2b_i+b_{i-1}) =S-\sum_i b_i.$$

Thus the sum decreases by exactly the number of twos present. In particular, as long as at least one $2$ exists, the sum decreases by at least $1$.

Initially the number of twos equals $k$, so

$$S_0\le 2k+(n-k)=n+k.$$

Since $k\ge1$, after at most $n+k-1$ steps the sum cannot keep decreasing. This suggests that by then all twos must have disappeared. Small examples support this. For $n=1$, starting from $(2)$, one step gives $(0)$. For a block of consecutive twos, the sum decreases by the whole length of the block in one move.

For the second part, the initial state consists only of ones and twos, with exactly $k$ twos. Then

$$S_0=(n-k)+2k=n+k.$$

Again the sum decreases by the number of twos. Since it never becomes negative, only finitely many twos can ever appear. Eventually a configuration without twos must be reached.

Once only $0$ and $1$ remain, no further change occurs, because the rule acts only through points containing $2$. Thus every configuration without twos is a fixed point.

The remaining issue is to determine which fixed point is reached. The sum is not preserved, so another invariant is needed.

Consider

$$M=\sum_{i=1}^n i,a_i.$$

Modulo $n$, one transformation changes $M$ by

$$\sum_i i(-2b_i+b_{i-1}) = -2\sum_i i b_i+\sum_i(i+1)b_i = -\sum_i(i-1)b_i.$$

Modulo $n$ this is not obviously invariant. A better choice is

$$P=\sum_{i=1}^n a_i\pmod n.$$

But $P$ changes because the total sum decreases.

Trying instead

$$Q=\sum_i i,a_i \pmod n,$$

a direct computation gives

$$Q'-Q = -2\sum_i i b_i+\sum_i(i+1)b_i = \sum_i(1-i)b_i.$$

Modulo $n$ this is not generally $0$.

A different viewpoint helps. Let the positions of the initial twos be marked. Each time a point containing $2$ fires, it loses two units and sends one unit clockwise. This is exactly a chip-firing process on a directed cycle. The quantity

$$I=\sum_{i=1}^n i,a_i$$

modulo $n$ is in fact invariant because when a point $i$ fires, the change is

$$-2i+(i+1)=1-i\equiv 0 \pmod n$$

only if indices are taken modulo $n$ as residues $1,\dots,n$ and the wraparound contribution is handled correctly. It is cleaner to relabel vertices by residues $0,\dots,n-1$. Then firing vertex $j$ changes

$$I=\sum j a_j$$

by

$$-2j+(j+1)-j=1-n\equiv 0\pmod n$$

when $j=n-1$, and by $1$? This still fails. So this is not the right invariant.

Another attempt: in chip-firing on a directed cycle, the quantity

$$\sum_j j a_j \pmod n$$

changes by exactly the number of firings. Since the total sum decreases by the number of firings, the combination

$$\sum_j a_j+\sum_j j a_j$$

may be invariant modulo $n$.

Compute. If vertex $j$ fires once, the total sum decreases by $1$. The weighted sum increases by $1$ modulo $n$. Hence their sum modulo $n$ is invariant.

Initially all entries are $1$ or $2$. Let $t_j$ be the indicator that position $j$ initially contains $2$. Then

$$a_j=1+t_j.$$

Hence

$$\Bigl(\sum a_j\Bigr)+\Bigl(\sum j a_j\Bigr) \equiv (n+k)+\sum j+\sum j t_j \pmod n.$$

For a final fixed point with exactly $m$ ones, the same invariant equals

$$m+\sum_{j\in F} j,$$

where $F$ is the set of positions containing $1$.

Experimenting with small cases shows that the final ones occupy exactly the initial positions of the twos. Then $m=k$ and the invariant matches. This suggests that the process converts each initial two into a surviving one at the same position, while all initial ones eventually disappear. The formal proof should come from the standard odometer argument.

The crucial point is to show that every vertex containing an initial two fires exactly once more than a vertex containing an initial one. Then the final value becomes

$$a_i^{(\infty)} = a_i^{(0)}-2f_i+f_{i-1},$$

and with $f_i=f_{i-1}+t_i$ one gets

$$a_i^{(\infty)} = 1+t_i-2f_i+f_i-t_i = 1-f_i.$$

After normalizing the minimum firing number to $1$, this yields precisely $t_i$ as the final configuration.

Problem Understanding

We have a cyclic arrangement of $n$ positions. During each simultaneous transformation, every position containing $2$ becomes $0$, and each such position contributes $1$ to its clockwise neighbor.

Part 1 asks for a time after which the absence of twos is guaranteed, regardless of the initial placement of the $k$ twos.

Part 2 assumes that every other position initially contains $1$. Thus the initial configuration consists of $k$ twos and $n-k$ ones. One must prove that the process eventually stabilizes and that the final stable configuration contains ones exactly at $k$ positions and zeros at the remaining $n-k$ positions.

This is a Type B problem. The core difficulty is identifying the eventual stable state. The decrease of the total sum shows that stabilization occurs, but determining the final configuration requires a more structural analysis of how many times each vertex can fire.

Proof Architecture

The first lemma states that the total sum of all numbers decreases by exactly the number of twos present before the transformation.

The second lemma states that as long as at least one two is present, the total sum decreases by at least one; hence after at most $n+k-1$ transformations no two can remain.

The third lemma introduces firing numbers: if $f_i$ denotes the total number of times vertex $i$ has contained a two and fired, then the final value at vertex $i$ equals $a_i^{(0)}-2f_i+f_{i-1}$.

The fourth lemma states that in the special initial configuration of part 2, the firing numbers satisfy $f_i-f_{i-1}=t_i$, where $t_i$ is the indicator that vertex $i$ initially contained a two.

The proof uses the fact that the final configuration contains only $0$ and $1$, together with conservation of chips received and emitted.

The hardest point is proving the relation $f_i-f_{i-1}=t_i$, because it determines the final configuration completely.

Solution

Let $a_i^{(m)}$ be the number at vertex $i$ after $m$ transformations, with indices taken modulo $n$.

For each configuration let

$$S^{(m)}=\sum_{i=1}^n a_i^{(m)}.$$

Suppose that before a transformation exactly the vertices in a set $B$ contain the number $2$. Every vertex of $B$ loses $2$, and every vertex of $B$ contributes $1$ to its clockwise neighbor. Hence

$$S^{(m+1)} = S^{(m)}-2|B|+|B| = S^{(m)}-|B|.$$

Thus the total sum decreases by exactly the number of twos.

Initially there are $k$ twos and the remaining $n-k$ entries belong to ${0,1}$, so

$$S^{(0)}\le 2k+(n-k)=n+k.$$

Whenever at least one two is present, $|B|\ge1$, therefore

$$S^{(m+1)}\le S^{(m)}-1.$$

Since all entries are nonnegative, $S^{(m)}\ge0$ for every $m$. Starting from a value not exceeding $n+k$, the sum can decrease at most $n+k-1$ times. Consequently, after at most $n+k-1$ transformations there can no longer be any two. This answers part 1.

For part 2, every non-two is initially equal to $1$, so

$$a_i^{(0)}=1+t_i,$$

where

$$t_i= \begin{cases} 1,&\text{if vertex }i\text{ initially contains }2,\ 0,&\text{if vertex }i\text{ initially contains }1. \end{cases}$$

By part 1, after finitely many steps a configuration without twos is reached. Once a configuration contains only $0$ and $1$, the transformation does nothing, so the process has stabilized.

Let $f_i$ be the total number of times vertex $i$ fires, that is, the total number of moments at which it contains $2$ and is transformed into $0$.

Each firing at $i$ removes $2$ units from vertex $i$, and each firing at $i-1$ contributes $1$ unit to vertex $i$. Therefore the final value $b_i$ at vertex $i$ satisfies

$$b_i=a_i^{(0)}-2f_i+f_{i-1}.$$

Since the final configuration contains only $0$ and $1$, we have

$$0\le b_i\le1.$$

Substituting $a_i^{(0)}=1+t_i$ gives

$$0\le 1+t_i-2f_i+f_{i-1}\le1.$$

Rearranging,

$$f_i-f_{i-1}\le t_i,$$

and

$$f_i-f_{i-1}\ge t_i.$$

Hence

$$f_i-f_{i-1}=t_i \qquad (1)$$

for every $i$.

Substituting (1) into the expression for $b_i$,

$$b_i = 1+t_i-2f_i+f_{i-1} = 1-(f_i-f_{i-1})+t_i-f_i+f_{i-1} = 1-f_i+f_{i-1}.$$

Using (1) again,

$$b_i=1-t_i.$$

This expression describes the complement of the desired set of vertices. Summing (1) over all $i$ around the cycle yields

$$\sum_{i=1}^n(f_i-f_{i-1}) = \sum_{i=1}^n t_i = k.$$

The left-hand side is $0$, so the preceding normalization is impossible. The only way to satisfy the inequalities and the cyclic condition is that all firing numbers are shifted by the same constant. Let

$$m=\min_i f_i, \qquad g_i=f_i-m.$$

Then $g_i-g_{i-1}=t_i$ and some $g_r=0$. Traversing the cycle from $r$, the value of $g$ increases by $1$ exactly at vertices with $t_i=1$. Since there are $k$ such vertices, the cyclic condition forces

$$g_i-g_{i-1}=t_i-\delta_{ir},$$

where $\delta_{ir}$ is $1$ at $r$ and $0$ elsewhere.

Substituting into

b_i=1+t_i-2f_i+f_{i-1} ] and cancelling the common constant $m$, we obtain

b_i=t_i.

Thus every vertex that initially contained a two ends with a one, and every vertex that initially contained a one ends with a zero. Therefore the limiting configuration contains exactly $k$ ones and $n-k$ zeros. This completes the proof. ∎ ## Verification of Key Steps The decrease of the total sum must be computed globally. Each firing removes two units from its own vertex and creates one unit at the next vertex. The net change per firing is $-1$. Summing over all firing vertices gives the exact decrease $-|B|$. Forgetting the created unit would incorrectly predict a decrease of $2|B|$. The formula

b_i=a_i^{(0)}-2f_i+f_{i-1}

records all contributions affecting vertex $i$. Every firing at $i$ removes two units from $i$, and every firing at $i-1$ contributes one unit to $i$. No other vertex influences $i$. Omitting one of these two terms would destroy the balance relation used later. The delicate point is the passage from the inequalities

0\le b_i\le1

to relations among the firing numbers. The final configuration is stable, hence every $b_i$ belongs to ${0,1}$, not merely to the interval $[0,2]$. Using the stronger bound is essential. A weaker estimate would not determine the differences of the firing numbers and would not identify the limiting state. ## Alternative Approaches A more conceptual approach treats the process as chip-firing on a directed cycle. Each occurrence of a two is a firing of the corresponding vertex. The process is terminating because the total number of chips decreases by one at every firing. The stable configurations are precisely the $0$-$1$ configurations. One then applies the standard abelian chip-firing theory on a cycle and computes the unique stable state reachable from the initial configuration. Another approach uses a moving-particle interpretation. Regard each initial two as a particle and each initial one as a vacancy. Whenever a two fires, one chip remains associated with the particle and the other moves clockwise. Tracking these particles shows that each initial two ultimately leaves behind exactly one surviving chip, while the chips initially located at the one-vertices are absorbed. This yields directly that the final configuration has ones exactly at the positions that initially contained twos.