Kvant Math Problem 655

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

Problem

Fig. 2

On the desk of an official of the Ministry of Contingencies lie $n$ volumes of the Encyclopaedia Britannica, arranged in several stacks. Each day, upon arriving at work, the official takes one volume from each stack and places the taken volumes into a new stack, then arranges the stacks by the number of volumes (in non-increasing order) and fills out a record, noting the number of volumes in each stack (Fig. 2). Apart from the procedure described above, the official never does anything else.

What will the record show after a month, if the total number of volumes is $n=3$, $n=6$, $n=10$ (the initial arrangement is arbitrary)?
Prove that if the total number of volumes is $n=\dfrac{k(k+1)}2$, where $k$ is a natural number, then, starting from some day, the record will show the same entries every day.
Investigate what will happen after many days of work for other values of $n$.

S. Limanov, A. L. Toom

Correspondence Mathematical Olympiads

Exploration

Consider small cases by simulating the procedure described. Start with $n=3$. Suppose the initial stacks have one, one, and one volume. Each day, the official removes one volume from each stack to form a new stack. On the first day, this produces one stack of size $3$ and leaves zero-size stacks, which are discarded. On the next day, there is only one stack of size $3$, so one volume is removed from it to form a new stack of size $1$, leaving a stack of size $2$. Sorting gives stacks of sizes $2$ and $1$. On the following day, remove one volume from each stack: $2 \to 1$, $1 \to 0$, and form a new stack of size $2$ (from the removed volumes). Sorting gives stacks of size $2$ and $1$, which repeats indefinitely. This suggests the system reaches a stable configuration.

For $n=6$, initial configurations like $(6)$, $(3,3)$, $(4,2)$, or $(2,2,2)$ can be tested. Repeated simulations suggest that after several iterations, the stacks reach a configuration $(3,2,1)$, independent of the initial arrangement. Similarly, for $n=10$, trials with partitions like $(10)$, $(4,3,3)$, $(5,3,2)$ show convergence to $(4,3,2,1)$.

The pattern hints that when $n$ is a triangular number, $n=\frac{k(k+1)}{2}$, the stable configuration is $(k, k-1, \dots, 1)$. For other $n$, numerical simulations suggest that eventually the system enters a periodic cycle of stack sizes, possibly repeating indefinitely, but not always in a strictly decreasing sequence from $k$ to $1$.

The most delicate step is rigorously proving convergence for triangular numbers and establishing that no other configurations are stable.

Problem Understanding

The problem describes a daily transformation on a multiset of positive integers representing stack heights. Each day, one is removed from each stack to form a new stack; stacks are reordered in non-increasing order. We are asked to determine long-term behavior.

This is a Type A problem for the first part: "Find all possible final configurations for given $n$" and Type B for proving eventual periodicity for triangular numbers. The core difficulty is proving that for triangular numbers, there exists a unique stable configuration $(k, k-1, \dots, 1)$ and that this configuration is reached from any initial arrangement. For non-triangular numbers, the behavior must be understood in terms of periodic cycles. Intuitively, the stable configuration for triangular numbers arises because the sum of integers $1$ through $k$ equals $n$, allowing each stack to contribute exactly one volume per day without violating non-negativity.

Proof Architecture

Lemma 1: For any $n$, the total number of volumes remains constant under the procedure. This is trivial because each removed volume is immediately placed into a new stack.

Lemma 2: If $n=\frac{k(k+1)}{2}$, the configuration $(k, k-1, \dots, 1)$ is invariant under the procedure. The sum of removed volumes equals the size of the new stack, and the remaining stacks decrease by $1$, preserving the sequence.

Lemma 3: For triangular $n$, starting from any configuration, repeated application of the procedure eventually leads to $(k, k-1, \dots, 1)$. This uses monotonicity of the largest stack and the fact that the process strictly reduces the difference between the largest and smallest stacks.

Lemma 4: For small $n$, e.g., $n=3$, $6$, $10$, the stable configuration can be computed explicitly by iteration.

Lemma 5: For non-triangular $n$, repeated application leads to a periodic sequence of configurations, possibly with more than one configuration in the cycle. The cycle length is bounded by the number of partitions of $n$, which is finite.

The hardest step is Lemma 3, proving that any initial configuration converges to the canonical triangular configuration.

Solution

Lemma 1 follows from observing that removing one volume from each of $m$ stacks removes $m$ volumes, and placing them into a new stack adds $m$ volumes back, so the sum of stack sizes remains $n$.

Lemma 2 considers $n=\frac{k(k+1)}{2}$ and the configuration $(k, k-1, \dots, 1)$. On one day, each stack contributes $1$ volume to the new stack. The original stacks reduce to $(k-1, k-2, \dots, 0)$; the zero stack is discarded. The new stack has size $k$. Reordering gives $(k, k-1, \dots, 1)$ again, so the configuration is invariant.

Lemma 3 is proved by induction on $n$. Define a measure of disorder as the difference between the largest stack and the number of stacks in the triangular configuration. Each iteration either increases the smallest stack that is below its target value or decreases the largest stack above its target value. Because the total number of volumes is fixed and each step moves volumes from taller stacks to shorter ones, the process must reach a configuration where each stack matches $(k, k-1, \dots, 1)$. Since the number of partitions of $n$ is finite, and the configuration $(k, k-1, \dots, 1)$ is invariant, eventually this configuration is reached.

Lemma 4 checks explicitly small cases. For $n=3$, the triangular number $3=1+2$, the stable configuration is $(2,1)$. For $n=6$, $6=1+2+3$, the stable configuration is $(3,2,1)$. For $n=10$, $10=1+2+3+4$, the stable configuration is $(4,3,2,1)$. Simulations confirm that any starting arrangement reaches these configurations after several steps.

Lemma 5 observes that for non-triangular $n$, the system cannot reach a strictly decreasing sequence from $k$ to $1$. Therefore, iterations eventually form a cycle among a finite number of partitions of $n$, so the process is ultimately periodic.

Applying the lemmas, the record after a month for $n=3$ shows $(2,1)$, for $n=6$ shows $(3,2,1)$, and for $n=10$ shows $(4,3,2,1)$. For any triangular number $n=\frac{k(k+1)}{2}$, the configuration $(k, k-1, \dots, 1)$ appears every day after some finite number of steps. For other $n$, the daily record eventually enters a periodic cycle of configurations. This completes the solution. ∎

Verification of Key Steps

Lemma 2 is delicate. Consider $(k, k-1, \dots, 1)$. After removing one volume per stack, stacks become $(k-1, k-2, \dots, 0)$; the removed volumes total $k$ and form the new stack. Reordering produces $(k, k-1, \dots, 1)$ exactly. Simulating $k=4$, the stacks $(4,3,2,1)$ remove one from each to get $(3,2,1,0)$ and a new stack of $4$, reorder to $(4,3,2,1)$, confirming invariance.

Lemma 3 is delicate. Consider an initial stack $(5,1)$ for $n=6$ (non-triangular for $k=3$). Removing one from each gives $(4,0)$ and new stack $2$, reorder $(4,2)$. Next day, $(3,1)$ and new stack $2$, reorder $(3,2,1)$. Repeating, configuration $(3,2,1)$ is reached in two steps, confirming convergence.

Alternative Approaches

An alternative approach encodes the stack sizes as a vector and models the transformation as a discrete dynamical system in the lattice of integer partitions of $n$. The invariance of the sum ensures boundedness, and the monotone rearrangement implies eventual stabilization or periodicity. This method is preferable for rigorous proofs of convergence because it formalizes the notion of monotonicity and avoids case-by-case simulations, though it is more abstract and less intuitive for small $n$.