Kvant Math Problem 1349

Verified: no
Verdicts: SKIP + SKIP
Solve time: 10m23s
Source on kvant.digital

Problem

The circle is divided into $n$ sectors. Some of them contain counters; in total there are $n+1$ counters. The position is then subjected to the following transformations: any two counters located in the same sector are taken and moved in opposite directions into the neighboring sectors. Prove that after a certain number of such transformations, at least half of the sectors will be occupied by counters.

D. V. Fomin

Tournament of Towns

Exploration

Let $a_i$ be the number of counters in sector $i$, with indices taken modulo $n$. A move replaces

$$(a_{i-1},a_i,a_{i+1})$$

by

$$(a_{i-1}+1,\ a_i-2,\ a_{i+1}+1)$$

whenever $a_i\ge 2$.

The total number of counters is preserved. We start with

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

The process resembles chip-firing on a cycle. A natural first guess is that eventually every sector contains at most one counter. Since there are $n+1$ counters and only $n$ sectors, that is impossible. Hence the process cannot terminate in a configuration with all $a_i\le1$.

Try small examples.

For $n=3$, starting from $(4,0,0)$:

$$(4,0,0)\to(2,1,1)\to(0,2,2)\to(1,0,3)\to\cdots$$

The process does not stop, but already two sectors are occupied, which is at least half of $3$.

For $n=4$, starting from $(5,0,0,0)$:

$$(5,0,0,0)\to(3,1,0,1)\to(1,2,0,2).$$

Now all four sectors are occupied after one more move.

The statement asks only for existence of some moment when at least half the sectors are occupied. This suggests looking for a quantity that increases and is bounded.

Let

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

If a move is performed at sector $i$, where $a_i=k\ge2$, then

$$\Delta E =(k-2)^2-(k^2) +(a_{i-1}+1)^2-a_{i-1}^2 +(a_{i+1}+1)^2-a_{i+1}^2.$$

After simplification,

$$\Delta E =-4k+4+2a_{i-1}+1+2a_{i+1}+1 =2(a_{i-1}+a_{i+1}-2k)+6.$$

Since the total number of counters is $n+1$, this expression is not always negative. Thus $E$ is not the right invariant.

A standard invariant for chip-firing on a cycle is

$$Q=\sum a_i^2.$$

Recompute more carefully:

$$\Delta Q =(k-2)^2-k^2 +(b+1)^2-b^2 +(c+1)^2-c^2$$

with $b=a_{i-1}$ and $c=a_{i+1}$.

Hence

$$\Delta Q =(-4k+4)+(2b+1)+(2c+1) =2(b+c-2k+3).$$

This can be positive, so $Q$ is not monotone.

Another possibility is to study configurations with fewer than half the sectors occupied. Suppose only $m<n/2$ sectors are occupied. Then $n+1$ counters are distributed among $m$ sectors, so some occupied sector contains at least

$$\left\lceil\frac{n+1}{m}\right\rceil\ge3$$

counters. Thus a move is possible. Therefore any configuration with fewer than half the sectors occupied cannot be stable.

This is promising. If we can show that the process must eventually reach a stable configuration, then such a stable configuration would necessarily have at least half the sectors occupied.

The crucial question becomes: does every sequence of legal moves terminate?

For a cycle, chip-firing usually does not terminate when the total number of chips is at least $n$. Here the total is $n+1$, so termination is false.

Hence we need a different idea.

Consider the quantity

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

A firing at sector $i$ sends one counter to each neighbor. The contribution changes by

$$(i-1)+(i+1)-2i=0,$$

so $F$ is invariant mod $n$.

Chip-firing theory on a cycle says that with $n+1$ chips every legal process eventually becomes periodic, and the only recurrent configurations have exactly one sector containing $2$ counters and all others containing $1$. Such configurations occupy all $n$ sectors. That would prove the statement.

A more elementary route is needed.

Let

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

A firing at sector $i$ changes $P$ by $n$ or $-n$ depending on wrap-around, hence $P$ modulo $n$ is invariant. More importantly, define

$$H=\sum_{i=1}^n a_i(a_i-1).$$

A calculation gives

$$\Delta H =2(b+c-2k+2).$$

Not monotone.

The standard potential for chip-firing on a cycle is

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

Compute the effect of firing at $i$ away from the boundary:

$$(i-1)^2+(i+1)^2-2i^2=2.$$

Thus every firing increases $\Phi$ by $2$. Modulo the cyclic indexing there are wrap-around corrections, but by choosing representatives on the infinite line after cutting the cycle at a suitable place, one obtains a strictly increasing bounded-above potential as long as some sector stays empty. This is the key.

Take an empty sector and cut the circle there. Then the sectors become a line $1,\dots,n$. While that chosen sector remains empty, every move occurs at an interior vertex and increases

$$\Phi=\sum i^2 a_i$$

by exactly $2$. Since the total number of counters is fixed, $\Phi$ is bounded above. Hence only finitely many moves can occur before the chosen sector becomes occupied.

Therefore every empty sector eventually gets occupied. If initially fewer than half the sectors are occupied, then more than half are empty. Choose one of the empty sectors. Eventually it becomes occupied. Repeating, the number of occupied sectors must increase until at least half are occupied. The delicate point is to justify repetition.

Indeed, whenever the number of occupied sectors is still less than $n/2$, there exists an empty sector. Fix such a sector. As long as it remains empty, $\Phi$ strictly increases, so after finitely many moves it must become occupied. Thus from any configuration with fewer than half the sectors occupied, after finitely many further moves the number of occupied sectors increases by at least one. Repeating finitely many times yields at least half occupied sectors.

That seems to be the intended argument.

Problem Understanding

We have $n$ sectors arranged in a circle and $n+1$ counters distributed among them. A legal transformation chooses a sector containing at least two counters, removes two counters from that sector, and places one counter in each neighboring sector.

We must prove that after finitely many legal transformations there is a position in which at least half of the sectors contain a counter.

This is a Type B problem. The task is to prove the stated property.

The core difficulty is that the process need not terminate. One must show directly that whenever fewer than half of the sectors are occupied, the number of occupied sectors can be forced to increase after finitely many further moves.

Proof Architecture

Lemma 1. If a sector is fixed and remains empty during a sequence of moves, then after cutting the circle at that sector and numbering the remaining sectors $1,\dots,n$, the potential $\Phi=\sum i^2a_i$ increases by $2$ at every move.

The reason is that a firing at sector $i$ replaces two counters at position $i$ by one counter at each neighboring position, and $(i-1)^2+(i+1)^2-2i^2=2$.

Lemma 2. While the chosen sector remains empty, only finitely many moves are possible.

The reason is that $\Phi$ increases by $2$ at every move but is bounded above because the total number of counters equals $n+1$.

Lemma 3. If a sector is empty, then after finitely many moves it becomes occupied.

The reason is that otherwise infinitely many moves would occur while that sector stayed empty, contradicting Lemma 2.

Main step. If fewer than half the sectors are occupied, choose an empty sector. By Lemma 3 it becomes occupied after finitely many moves, so the number of occupied sectors increases by at least one. Repeating this argument finitely many times yields a position with at least half the sectors occupied.

The most delicate point is Lemma 1, because one must verify carefully that cutting the circle at an empty sector prevents any move across the cut.

Solution

Assume that at some moment fewer than half of the sectors are occupied. We shall prove that after finitely many further transformations the number of occupied sectors increases.

Choose an empty sector $E$. Cut the circle at $E$ and number the remaining sectors consecutively by

$$1,2,\dots,n,$$

with $E$ lying between sectors $1$ and $n$.

As long as $E$ remains empty, no counter can pass through the cut. Indeed, a counter can enter $E$ only as the result of a transformation in sector $1$ or sector $n$, and at the first moment this happens the sector $E$ ceases to be empty. Thus, during every move performed before that moment, the sectors behave exactly like a line of $n$ positions.

Let $a_i$ be the number of counters in sector $i$, and define

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

Consider a transformation performed in sector $i$. Let $a_i=k\ge2$. One counter moves from $i$ to $i-1$ and one counter moves from $i$ to $i+1$. The change in $\Phi$ is

$$(i-1)^2+(i+1)^2-2i^2 = i^2-2i+1+i^2+2i+1-2i^2 =2.$$

Hence every legal transformation increases $\Phi$ by exactly $2$.

On the other hand, the total number of counters is always $n+1$. Therefore

$$\Phi =\sum_{i=1}^{n} i^2 a_i \le (n+1)n^2.$$

Thus $\Phi$ is bounded above.

Since $\Phi$ increases by $2$ at every transformation, only finitely many transformations can occur while the sector $E$ remains empty.

Consequently, the sector $E$ cannot stay empty forever. After finitely many transformations it must receive a counter and become occupied.

We have proved the following statement: whenever a configuration has an empty sector, after finitely many further transformations the number of occupied sectors increases by at least one.

Now return to the original situation. If at some moment fewer than half of the sectors are occupied, then there is at least one empty sector. By the statement just proved, after finitely many transformations the number of occupied sectors increases. If it is still less than half of $n$, there is again an empty sector, and the same argument applies once more.

Each application increases the number of occupied sectors by at least one. Since there are only finitely many sectors, after finitely many repetitions we reach a position in which at least half of the sectors are occupied.

This completes the proof.

∎

Verification of Key Steps

The first delicate step is the computation of the change of $\Phi$. A firing in sector $i$ removes two counters from position $i$ and adds one counter to each neighboring position. The contribution of all other counters is unchanged. Hence

$$\Delta\Phi =(i-1)^2+(i+1)^2-2i^2 =2.$$

The positive constant $2$ is independent of $i$. Any mistake in this calculation would destroy the monotonicity argument.

The second delicate step is the treatment of the cut. The proof uses the identity above for a line rather than a circle. This is valid only while the chosen sector $E$ is empty. If a move sent a counter across the cut, that counter would enter $E$, so $E$ would cease to be empty. Thus every move performed before the first occupation of $E$ takes place entirely within the line $1,\dots,n$.

The third delicate step is the iteration. The argument does not require the process to terminate. Starting from a configuration with fewer than $n/2$ occupied sectors, we choose an empty sector and wait until it becomes occupied. This increases the number of occupied sectors by at least one. If the new configuration still has fewer than $n/2$ occupied sectors, there is again an empty sector and the same reasoning applies. Since the number of occupied sectors increases by an integer at each stage and never exceeds $n$, only finitely many stages are needed.

Alternative Approaches

A more advanced approach uses chip-firing theory on a cycle. The transformation is exactly a chip-firing move. For a cycle with $n+1$ chips, every legal evolution eventually reaches a recurrent configuration. The recurrent configurations consist of $n-1$ sectors containing one counter, one sector containing two counters, and no empty sectors. Hence all $n$ sectors are occupied, which is stronger than required.

The potential-function argument is preferable here because it uses only an elementary invariant. It avoids the structure theory of recurrent chip-firing configurations and proves directly that whenever fewer than half the sectors are occupied, the number of occupied sectors must increase after finitely many further transformations.