Kvant Math Problem 11

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

Problem

Forty-four merry siskins were perched on 44 trees arranged in a circle (one siskin on each tree). From time to time, two siskins simultaneously fly to neighboring trees in opposite directions (one clockwise, the other counterclockwise; see Fig. 1). Prove that the siskins will never gather on a single tree.

What if the number of siskins and trees is $n$?

Evening Mathematical School at Moscow State University

Exploration

Label the trees by the residues modulo $n$, arranged around the circle. Initially tree $i$ contains one siskin.

A move consists of choosing two siskins. One flies from some tree $a$ to $a+1$, the other from some tree $b$ to $b-1$ modulo $n$. The total number of birds on each tree changes, but the total number of birds is preserved.

The first question is whether there is a quantity preserved by every move. The sum of the tree labels occupied by all birds is a natural candidate. If one bird moves clockwise, its label increases by $1$; if another moves counterclockwise, its label decreases by $1$. Hence the sum of occupied labels, counted with multiplicity, is unchanged modulo $n$.

For $n=44$, the initial value is

$$0+1+\cdots+43=\frac{44\cdot 43}{2}=946.$$

Modulo $44$ this equals $22$.

Suppose all $44$ birds gathered on a single tree $t$. Then the sum of occupied labels would be

$$44t\equiv 0 \pmod{44}.$$

Since $22\not\equiv 0\pmod{44}$, such a state cannot be reached.

This suggests the invariant

$$S=\sum (\text{labels of all birds}) \pmod n.$$

For general $n$, initially

$$S_0=0+1+\cdots +(n-1)=\frac{n(n-1)}2.$$

If all birds gather on one tree, the value becomes $0$ modulo $n$.

The question becomes: when is

$$\frac{n(n-1)}2\equiv 0\pmod n?$$

Write $n=2m$ or $n=2m+1$.

For odd $n$, division by $2$ is legitimate modulo $n$, and

$$\frac{n(n-1)}2=n\cdot \frac{n-1}{2},$$

which is divisible by $n$. Thus the invariant does not forbid gathering.

For even $n=2m$,

$$\frac{n(n-1)}2=m(n-1)\equiv -m\equiv m \pmod n.$$

This is nonzero modulo $n$ whenever $m>0$. Hence gathering is impossible for every even $n$.

To check that odd $n$ may actually allow gathering, test $n=3$. Starting from $(1,1,1)$ on the three trees, move the birds on trees $0$ and $1$. The configuration becomes $(0,2,1)$. Move a bird from tree $1$ clockwise and the bird from tree $2$ counterclockwise. The result is $(0,0,3)$. Gathering is indeed possible. Thus the parity distinction is likely the complete answer.

The step most likely to hide an error is proving that the invariant is preserved modulo $n$, because the circle involves wraparound. Working modulo $n$ handles this automatically.

Problem Understanding

There are $n$ trees arranged in a circle and initially one siskin sits on each tree. A move consists of selecting two siskins simultaneously; one flies to the next tree clockwise and the other to the next tree counterclockwise. The question is whether all siskins can ever end up on a single tree.

This is a Type B problem. The statement for $n=44$ must be proved, and then the general behavior for arbitrary $n$ must be determined.

The core difficulty is finding a quantity that remains unchanged under every allowed move and distinguishes the initial configuration from a configuration in which all birds occupy one tree.

Proof Architecture

Define the invariant $S$ as the sum of the labels of all birds, counted with multiplicity, modulo $n$; each move changes one summand by $+1$ and another by $-1$, so $S$ is preserved.

Compute the initial value $S_0=\frac{n(n-1)}2 \pmod n$.

If all birds occupy a single tree $t$, then $S\equiv nt\equiv0\pmod n$.

For even $n$, show that $\frac{n(n-1)}2\not\equiv0\pmod n$; hence gathering is impossible.

For odd $n$, show that $\frac{n(n-1)}2\equiv0\pmod n$; the invariant gives no obstruction.

Produce an explicit gathering process for odd $n$, proving that gathering is actually possible.

The most delicate point is the construction for odd $n$, because the invariant alone only proves impossibility for even $n$.

Solution

Number the trees by the residues

$$0,1,\dots,n-1$$

modulo $n$. For each bird, record the label of the tree on which it sits. Let

$$S$$

denote the sum of these labels, counted with multiplicity, taken modulo $n$.

Consider one move. One bird moves from some tree $a$ to $a+1$, while another bird moves from some tree $b$ to $b-1$, all labels being interpreted modulo $n$. The contribution of the first bird to $S$ increases by $1$, and the contribution of the second decreases by $1$. Hence the total change of $S$ is

$$(+1)+(-1)=0 \pmod n.$$

Thus $S$ is an invariant of the process.

Initially there is one bird on each tree, so

$$S_0=0+1+\cdots +(n-1) =\frac{n(n-1)}2.$$

Suppose all $n$ birds are gathered on a single tree $t$. Then

$$S\equiv t+t+\cdots+t=nt\equiv0\pmod n.$$

Therefore gathering is possible only if

$$\frac{n(n-1)}2\equiv0\pmod n.$$

First let $n=44$. Then

$$S_0=\frac{44\cdot43}{2}=946\equiv22\pmod{44}.$$

Since a gathered configuration would have invariant $0$, such a configuration cannot be reached. Hence the $44$ siskins can never gather on a single tree.

Now consider arbitrary $n$.

Assume first that $n=2m$ is even. Then

$$S_0=\frac{n(n-1)}2=m(n-1)\equiv -m\equiv m\pmod n.$$

Since $0<m<n$, this residue is nonzero modulo $n$. Therefore the invariant of the initial configuration differs from the invariant of every gathered configuration. Gathering is impossible for every even $n$.

Assume now that $n$ is odd. Write

$$n=2k+1.$$

Then

$$S_0=\frac{n(n-1)}2 =nk,$$

which is divisible by $n$. Thus the invariant does not prevent gathering.

It remains to show that gathering can actually be achieved.

Let the trees be numbered modulo $n$, and choose tree $0$ as the destination. For each pair of trees

$$i,,-i \qquad (1\le i\le k),$$

move one bird from tree $i$ repeatedly counterclockwise until it reaches tree $0$, and simultaneously move one bird from tree $-i$ repeatedly clockwise until it reaches tree $0$. Each such simultaneous step is an allowed move. After exactly $i$ steps both birds arrive at tree $0$.

Perform this procedure for $i=1,2,\dots,k$. The pairs are disjoint because $n$ is odd. Every bird not initially on tree $0$ belongs to exactly one such pair, and each pair contributes its two birds to tree $0$. The bird initially on tree $0$ remains there throughout.

After all these operations, all $n$ birds are on tree $0$. Hence gathering is possible when $n$ is odd.

Consequently, the complete answer is:

$$\text{all birds can gather on one tree if and only if } n \text{ is odd}.$$

For $n=44$, which is even, gathering is impossible.

This completes the proof.

∎

Verification of Key Steps

The invariant must remain valid when a bird crosses from tree $n-1$ to tree $0$ or from tree $0$ to tree $n-1$. Working modulo $n$, the first move changes the label by

$$0-(n-1)\equiv1\pmod n,$$

and the second changes it by

$$(n-1)-0\equiv-1\pmod n.$$

Thus every clockwise move contributes $+1$ and every counterclockwise move contributes $-1$ modulo $n$, including wraparound cases.

For even $n=2m$, the residue of the initial invariant is

$$m(n-1)\equiv -m\pmod n.$$

A careless simplification might replace this by $0$ because of the factor $n$. The factor $n$ has already been removed; what remains is $-m$, and since $0<m<n$, this residue is nonzero.

For odd $n$, the construction requires every nonzero tree to belong to exactly one pair ${i,-i}$. If ${i,-i}={j,-j}$ with $1\le i,j\le k$, then either $i=j$ or $i\equiv-j\pmod n$. The latter is impossible because $1\le i+j\le2k<n$. Hence the pairs are distinct and cover all nonzero trees.

Alternative Approaches

A different invariant uses the complex $n$th roots of unity. Place the weight $\omega^j$ on tree $j$, where $\omega=e^{2\pi i/n}$. Let $T$ be the sum of the weights of the trees occupied by the birds, counted with multiplicity. A clockwise move multiplies one contribution by $\omega$, while a counterclockwise move multiplies another by $\omega^{-1}$. The total effect is more complicated than for the linear invariant, but for even $n$ one can extract a preserved quantity related to parity classes of vertices. This approach is less transparent than the modular sum.

Another route is to assign alternating weights $+1,-1,+1,-1,\dots$ when $n$ is even. Every allowed move transfers one bird from an even tree to an odd tree and another from an odd tree to an even tree, so the weighted sum remains unchanged. Initially the sum is $0$, whereas a configuration with all birds on one tree has weighted sum $\pm n$. This proves impossibility for even $n$. The modular-sum invariant is preferable because it also yields the complete classification and naturally explains why odd $n$ behave differently.