Kvant Math Problem 870
Let the occupied rooms be represented by the multiset of integer positions of all pianists.
Verified: no
Verdicts: SKIP + SKIP
Solve time: 7m15s
Source on kvant.digital
Problem
Along one side of an infinite corridor, there is an infinite number of rooms, numbered consecutively with integers, and each contains a piano. A finite number of pianists live in these rooms. (Several pianists may live in the same room.) Each day, two pianists living in neighboring rooms — the $k$-th and $(k+1)$-th — realize that they are disturbing each other and move to the $(k-1)$-nd and $(k+2)$-rd rooms, respectively. Prove that after a finite number of days, these relocations will cease.
V. G. Ilyichyov
Cities Tournament (Spring, 1984)
Exploration
Let the occupied rooms be represented by the multiset of integer positions of all pianists. Only finitely many pianists exist, say $n$ of them.
A move occurs when two pianists occupy neighboring rooms $k$ and $k+1$. They move to $k-1$ and $k+2$. The distance between these two particular pianists changes from $1$ to $3$.
The first quantity to test is the sum of positions. If the two pianists are at $k$ and $k+1$, after the move they are at $k-1$ and $k+2$, so the sum changes from $2k+1$ to $(k-1)+(k+2)=2k+1$. Hence the total sum of all positions is invariant.
An invariant alone does not imply termination. We need a quantity that changes monotonically.
Consider the sum of squares of positions. For the moving pair,
$$(k-1)^2+(k+2)^2-\bigl(k^2+(k+1)^2\bigr) =2.$$
Thus every move increases the total sum of squares by exactly $2$.
To conclude, this quantity must be bounded above. Since there are only finitely many pianists and the total sum of positions is fixed, perhaps the positions cannot spread indefinitely.
Let the total sum of positions be $S$. If some pianist were at position $x>S$, then the sum of the remaining $n-1$ positions would be $S-x<0$. Since room numbers extend through all integers, this alone does not give a contradiction. A stronger argument is needed.
The move preserves the order of pianists along the corridor. If we label the pianists once and for all from left to right, then a move applied to two neighboring rooms sends the left pianist one step left and the right pianist one step right. Their order cannot change, because the new positions differ by $3$.
Hence each labeled pianist keeps the same rank. Let the initial positions of the labeled pianists be
$$a_1\le a_2\le\cdots\le a_n.$$
Since rank is preserved, at every later time the $i$-th pianist always has at least $i-1$ pianists to his left. Therefore his position cannot be smaller than $a_1-(i-1)$. Similarly, he cannot exceed $a_n+(n-i)$.
Indeed, to place the $i$-th pianist farther left than $a_1-(i-1)$ would require at least $i-1$ distinct integer rooms still farther left, which is impossible. The analogous argument gives the upper bound.
Thus every pianist remains in a fixed finite interval depending only on the initial configuration. Consequently the sum of squares of positions is bounded above. Since each move increases it by $2$, only finitely many moves can occur.
The delicate point is proving the uniform bounds on each pianist from preservation of order.
Problem Understanding
We have finitely many pianists occupying integer-numbered rooms on an infinite corridor. Whenever two pianists occupy neighboring rooms $k$ and $k+1$, they may move apart to rooms $k-1$ and $k+2$. We must prove that no matter how such relocations occur, after finitely many days no further relocation is possible.
This is a Type B problem. We must prove a given statement.
The core difficulty is finding a quantity that changes in only one direction under every move and showing that this quantity cannot increase indefinitely. The move increases distances, suggesting the use of a quadratic potential, but one must also prove that the positions of the pianists remain uniformly bounded.
Proof Architecture
Lemma 1. The left-to-right order of the pianists never changes. Sketch: during a move the two participating pianists remain three rooms apart, with the left one still left of the right one.
Lemma 2. If the pianists are labeled initially from left to right as $P_1,\dots,P_n$, then for every time and every $i$,
$$a_1-(i-1)\le x_i\le a_n+(n-i),$$
where $a_j$ are the initial positions and $x_i$ is the current position of $P_i$. Sketch: order preservation implies there must be at least $i-1$ distinct occupied rooms to the left of $P_i$ and at least $n-i$ distinct occupied rooms to its right.
Lemma 3. The quantity
$$Q=\sum_{i=1}^n x_i^2$$
increases by exactly $2$ at every relocation. Sketch: compute the change for the two moving pianists.
Lemma 4. The quantity $Q$ is bounded above. Sketch: Lemma 2 confines every pianist to a finite interval.
The hardest step is Lemma 2, because the proof requires extracting explicit position bounds from order preservation.
Solution
Label the $n$ pianists once and for all according to their left-to-right order at the initial moment. If several pianists occupy the same room, choose any order among them. Let their initial positions be
$$a_1\le a_2\le\cdots\le a_n.$$
Denote by $x_i$ the current position of the pianist $P_i$.
We first show that the order of the labeled pianists never changes. Suppose a move is performed by pianists occupying rooms $k$ and $k+1$. The pianist in room $k$ moves to $k-1$, and the pianist in room $k+1$ moves to $k+2$. After the move their positions are still ordered as
$$k-1<k+2.$$
No other pianist moves. Hence no pair of pianists can exchange their left-to-right order. Thus the order
$$P_1,P_2,\dots,P_n$$
is preserved throughout the process.
We next derive bounds for each $x_i$.
Since order is preserved, the pianists $P_1,\dots,P_{i-1}$ always lie at positions strictly smaller than $x_i$. These positions are distinct integers. Therefore there are at least $i-1$ distinct integers smaller than $x_i$ occupied by pianists. Consequently,
$$x_i\ge a_1+(i-1)-(i-1)=a_1-(i-1).$$
A more explicit argument is the following. If $x_i<a_1-(i-1)$, then there would be fewer than $i-1$ integers strictly between $-\infty$ and $x_i$, counted from $a_1-(i-1)$ upward, available for the positions of $P_1,\dots,P_{i-1}$, contradicting their required placement to the left of $P_i$.
Applying the same reasoning on the right side, the pianists $P_{i+1},\dots,P_n$ must occupy $n-i$ distinct integer positions strictly larger than $x_i$. Hence
$$x_i\le a_n+(n-i).$$
Thus every pianist remains inside the fixed finite interval
$$a_1-(n-1)\le x_i\le a_n+(n-1).$$
Now consider the quantity
$$Q=\sum_{i=1}^n x_i^2.$$
Suppose a move is performed by pianists in rooms $k$ and $k+1$. The contribution of these two pianists to $Q$ changes by
$$(k-1)^2+(k+2)^2-k^2-(k+1)^2.$$
A direct calculation gives
$$(k^2-2k+1)+(k^2+4k+4)-k^2-(k^2+2k+1)=2.$$
Therefore every relocation increases $Q$ by exactly $2$.
By the bounds established above, every $x_i$ belongs to a finite interval independent of time. Hence $Q$ is bounded above by
$$n\max!\left{(a_1-(n-1))^2,,(a_n+(n-1))^2\right}.$$
Thus $Q$ is an integer-valued quantity that increases by $2$ at each move and yet has a finite upper bound. Only finitely many moves are therefore possible.
After finitely many days no further relocation can occur. This completes the proof.
∎
Verification of Key Steps
The first delicate point is the preservation of order. If two pianists at $k$ and $k+1$ moved to positions that crossed, then labeling by rank would fail. The actual move sends them to $k-1$ and $k+2$, and
$$k-1<k+2.$$
Since every other pianist stays fixed, no inversion of order can ever be created.
The second delicate point is the upper and lower bounds on each labeled pianist. Consider $P_i$. Because order is preserved, there must always be $i-1$ pianists strictly to its left. Distinct pianists occupy distinct positions whenever one is strictly left of another, so at least $i-1$ distinct integers lie to the left of $x_i$. This forces
$$x_i\ge a_1-(i-1).$$
The symmetric argument yields
$$x_i\le a_n+(n-i).$$
A careless argument that only uses the invariance of the total sum of positions would not provide any bound on individual positions.
The third delicate point is the change in the quadratic potential. The computation must be exact:
$$(k-1)^2+(k+2)^2-\bigl(k^2+(k+1)^2\bigr)=2.$$
If the increase depended on $k$, boundedness of positions alone would not immediately imply termination. The constant increase by $2$ is what converts boundedness into finiteness of the process.
Alternative Approaches
Another proof uses the quantity
$$E=\sum_{i<j}(x_j-x_i)^2.$$
The total sum of positions is invariant under every move. Expanding $E$ gives
$$E=n\sum x_i^2-\left(\sum x_i\right)^2.$$
Since the second term is constant, $E$ increases by $2n$ whenever a move occurs. Order preservation again yields bounds on all positions, so $E$ is bounded above. Hence only finitely many moves are possible.
The approach with $Q=\sum x_i^2$ is preferable because the change under a move is immediately equal to $2$, requiring only a short computation and avoiding the introduction of pairwise distances.