Kvant Math Problem 500

Verified: no
Verdicts: UNKNOWN + UNKNOWN
Solve time: 9m26s
Source on kvant.digital

Problem

Fig. 1

Fig. 2

$N$ first-graders are lined up in a single row (shoulder to shoulder). On the command “left face,” everyone simultaneously turned by $90^\circ$; some turned to the left and others to the right. Exactly one second later, every person who finds themselves facing their neighbor turns “about-face” — by $180^\circ$. One second later, every person who is now facing a neighbor again turns by $180^\circ$, and so on (Fig. 1).

Prove that after a finite time the motion stops.
What is the maximum number of times one person could perform an “about-face” turn?
What is the maximum possible duration of the motion in the formation?
Suppose the line is infinite in both directions, and on the command “left face” only a finite set of $K$ first-graders turned to the right, while all others turned to the left. Then, according to the rule of the problem (given in italics), the motion would continue indefinitely. However, prove that the motion stops after a finite time if this rule is replaced by the following: a first-grader turns by $180^\circ$ only if the first (his neighbor) and the third person standing in front of him are facing him (Fig. 2).

G. Kurdyumov, Yu. Neretin

Exploration

Label the people $1,2,\dots,N$ from left to right. After the initial command each person is oriented either left (L) or right (R) relative to the line.

At any moment, only adjacent pairs matter. If person $i$ faces person $i+1$, then one must be facing right and the other facing left, so the pair has pattern $RL$ when read left to right. The rule applies exactly to such pairs: every occurrence of $RL$ becomes $LR$ after one second, since both individuals rotate by $180^\circ$.

Thus the evolution is a local rewriting rule

$$RL \to LR,$$

applied simultaneously at all occurrences.

A first observation is that this operation removes the configuration $RL$ at that edge, but it may create new $RL$ pairs at neighboring edges. Hence the dynamics is not trivially monotone in the number of “active” edges.

The key issue is whether these local changes can propagate indefinitely or whether each “disturbance” moves in a controlled direction and eventually exits the system.

Trying small configurations suggests that each initial mismatch behaves like a traveling object moving rightward: once an $RL$ becomes $LR$, the “disagreement” shifts one position to the right. This hints at a conservation law for the number of domain walls, together with a drift preventing cycles.

The most delicate point is to identify a quantity that strictly moves in one direction and therefore enforces finiteness of the process.

Problem Understanding

This is a Type B problem.

A row of $N$ people starts with arbitrary left/right orientations. At each second, every adjacent pair facing each other simultaneously flips both directions, turning an $RL$ pair into $LR$. The system evolves by local interactions.

We must prove that the process stabilizes in finite time, bound the number of flips a single person can perform, and determine the maximal duration of the process.

The core difficulty is that local updates can create new interacting pairs, so naive monotonicity arguments fail. The correct approach is to track how “disagreement interfaces” move through the system.

The expected outcome is that each such interface moves in a single direction and can traverse the entire row only finitely many times, which forces termination.

Proof Architecture

A first lemma identifies that the system can be encoded by adjacent pairs, and that only $RL$ pairs are active.

A second lemma shows that each application of the rule transforms a single active edge into an inactive one while shifting the effective location of interaction strictly to the right.

A third lemma proves that each active interface moves monotonically to the right and never returns to a previous position.

A fourth lemma deduces that each interface crosses each person at most once, implying a bound on the number of turns per person.

A fifth lemma shows that only finitely many interface moves are possible in a finite interval, giving termination and a bound on total time.

The hardest point is the monotonic drift of interfaces, since without a correct invariant one could incorrectly assume cancellation instead of propagation.

Solution

A pair of neighbors $i,i+1$ interacts exactly when they face each other, which occurs precisely when their orientations form the pattern $RL$ from left to right. When this happens, both rotate by $180^\circ$, so the pattern becomes $LR$.

Consider the configuration of adjacent pairs. Define an interface at position $i$ whenever the pair $(i,i+1)$ is $RL$. Only such interfaces trigger changes.

Fix one interface at position $i$. After one second, the pair at $i$ becomes $LR$. If no other interaction involved position $i$, the discrepancy that previously existed at $i$ is eliminated there. However, if one tracks where the next possible $RL$ configuration can arise involving $i+1$, one sees that any new interaction involving these two positions can only appear at $(i+1,i+2)$, never at $(i-1,i)$, since the left neighbor of $i$ is unaffected by the update at $(i,i+1)$.

Thus each interaction moves the effective site of activity weakly to the right. More precisely, if an interface is created at position $i$, then after its update, any subsequent interface involving those same two individuals can only be realized at a strictly larger index. Hence every “defect” propagates rightward.

Since there are only $N-1$ edges, any such defect can move at most $N-1$ steps before leaving the system. Therefore every initial interface generates at most $N-1$ interactions.

Each person changes orientation exactly when one of the two interfaces adjacent to them passes through that position. Since each interface passes any fixed position at most once, every person performs at most $N-1$ turns.

Since there are finitely many interfaces and each moves strictly rightward, after finitely many steps all interfaces exit the interval ${1,\dots,N-1}$. At that moment no adjacent pair faces each other, so no further motion is possible. Hence the process stops in finite time.

The maximal number of times one person can perform an about-face equals the maximal number of distinct interfaces that can pass through their position. In the worst case, one interface can pass through all positions in sequence, and there are at most $N-1$ such steps affecting a fixed person. Thus the maximum number of about-faces is

$$\boxed{N-1}.$$

To maximize the duration, arrange initial orientations so that a single interface traverses the entire row without interference, producing one interaction per time unit as it moves from position $1$ to position $N-1$. This yields $N-1$ steps before stabilization. No configuration can last longer because each interaction strictly advances an interface to a new edge and there are only $N-1$ edges. Hence the maximal duration is

$$\boxed{N-1}.$$

In the infinite-line variant with the modified rule, a person turns only when the first and third persons in front of him are both facing him. This condition involves a finite window of three consecutive positions. Any disturbance is therefore determined by a finite pattern and can only propagate when such a triple configuration is present.

Define a potential equal to the number of positions where a local configuration capable of triggering the rule occurs. Each application of the rule destroys the triggering configuration at its central point and shifts any possible creation of new triggering configurations strictly inside a bounded neighborhood. Since only finitely many sites initially violate uniform alignment, the set of possible active sites remains contained in a finite interval whose size cannot grow.

Each activation eliminates at least one occurrence of a triggering triple at its center, and no activation can reintroduce a previously eliminated central configuration at the same location. Hence the total number of activations is finite, forcing termination of the process in finite time.

Verification of Key Steps

The critical point is the claim that an interaction cannot propagate leftward. This follows from the locality of the update: only the states at positions $i$ and $i+1$ change during an update at $i$, and the left neighbor of $i$ does not depend on this change, so no new $RL$ pair can be created involving $(i-1,i)$ as a direct consequence of the update at $(i,i+1)$.

The second delicate point is the bound on how many times a fixed person can be involved. Each involvement corresponds to the passage of an interface across that position. Since an interface strictly shifts to the right after each activation and indices are bounded by $N$, no interface can cross a given position more than once.

The third point is termination. Because each interface move strictly increases its index and there are finitely many indices, infinite motion would require infinitely many strict increases in a finite set, which is impossible.

Alternative Approaches

One can encode the configuration as a binary string and interpret the evolution as a deterministic rewriting system $RL \to LR$. In this formulation, interfaces correspond to particles performing a rightward deterministic walk, and termination follows from the fact that all particles eventually exit a finite lattice.

Another approach uses a potential based on weighted inversions, assigning to each $RL$ pair a weight depending on its position. Each update strictly decreases a lexicographically ordered potential, which also forces finite termination, though it is less transparent than the interface propagation argument.