Problem 1972

Solution: The answer is $63766$.

We label the classrooms $c_1, c_2, \dots, c_{100}$. If $a_i$ students are in classroom $c_i$ for $1 \le i \le 100$ at a certain step in the process, denote by $(a_1, a_2, \dots, a_{100})$ the configuration of the students.

*Step 1:* We first show that $M$ is finite. Consider the function
$$f(a_1, a_2, \dots, a_{100}) = a_1^2 + a_2^2 + \dots + a_{100}^2.$$
If a student walks into room $a_i$ from room $a_j$, then we end up with the configuration $(a_1, a_2, \dots, a_i + 1, \dots, a_j - 1, \dots, a_{100})$ and
$$f(a_1, a_2, \dots, a_i + 1, \dots, a_j - 1, \dots, a_{100}) - f(a_1, a_2, \dots, a_{100}) = 2(a_i - a_j) + 2 \ge 2, \quad (41)$$
with equality if and only if $a_i = a_j$. Therefore, each move increases the value of $f$ by at least $2$.

On the other hand, it is easy to check that $f$ is maximized at
$$\mathcal{E} = (\underbrace{0, \dots, 0}_{99 \text{ 0's}}, 2010).$$
Because $f$ takes only positive values, we obtain that $M \le \frac{1}{2}f(\mathcal{E})$ is finite.

*Step 2:* Consider now the configuration
$$\mathcal{B} = (\underbrace{20, 20, \dots, 20}_{90 \text{ 20's}}, \underbrace{21, 21, \dots, 21}_{10 \text{ 21's}}).$$
We claim now that any configuration $\mathcal{C}$ may be reached from $\mathcal{B}$. Indeed, start from $\mathcal{C}$ and perform moves in reverse. In the reverse procedure, students may move from a room to a room with at least two fewer students. Observe that each reverse move decreases the value of $f$ by at least $2$ and that $\mathcal{B}$ is the only configuration where no reverse move is possible, meaning that performing a sequence of reverse moves starting at $\mathcal{C}$ until no more reverse moves are possible will yield $\mathcal{B}$. Inverting these reverse moves yields the desired sequence of moves from $\mathcal{B}$ to $\mathcal{C}$.

The claim implies that for any starting configuration $\mathcal{C}$, any sequence of moves from $\mathcal{C}$ to $\mathcal{E}$ may be extended to a sequence of moves from $\mathcal{B}$ to $\mathcal{E}$. Thus, to find the maximum value of $M$, it suffices for us to consider sequences of moves from $\mathcal{B}$ to $\mathcal{E}$.

*Step 3:* Consider now the special configuration
$$\mathcal{M} = (\underbrace{0, \dots, 0}_{38 \text{ 0's}}, 1, 2, 3, 4, 5, 7, 8, 9, \dots, 63).$$
Note that
$$f(\mathcal{M}) - f(\mathcal{B}) = (1^2 + 2^2 + \dots + 63^2 - 6^2) - (90 \cdot 20^2 + 10 \cdot 21^2) = 44898.$$
By (41), $f$ increases by at least $2$ at each step. Hence it takes at most $m_1 = 44898/2 = 22449$ steps to move from $\mathcal{B}$ to $\mathcal{M}$. We claim that this maximum of $m_1 = 22449$ steps can be achieved when moving from $\mathcal{B}$ to $\mathcal{M}$. By (41), a move decreases the value of $f$ by exactly $2$ if and only if it is between rooms with an equal number of students. Call these *good* moves. It therefore suffices to check that there exists a sequence of good moves changing $\mathcal{B}$ into $\mathcal{M}$. For this, we use the following lemma.

Lemma 1. For positive integers $1 \le a \le b$, if there is a set of $b-a+2$ rooms with configuration $(a, a+1, \dots, c-1, c, c+1, \dots, b-1, b)$ for some $a \le c \le b$, then there is a sequence of good moves which transforms these rooms into the configuration $(a-1, a, \dots, d-1, d+1, \dots, b+1)$ for $d=a+b-c$.

*Proof.* Let one of the students in a room with $c$ students move to the other room with $c$ students, then the one with $c+1$ students, and so on, until finally he reaches the room with $b$ students. At this point, the configuration is $(a, \dots, c-1, c-1, \dots, b-1, b+1)$. We may now repeat the procedure with the two rooms with $c-1$ students to reach the configuration $(a, \dots, c-2, c-2, \dots, b-2, b, b+1)$. After applying this procedure $c-a+1$ times, we arrive at $(a-1, a, \dots, d-1, d+1, \dots, b+1)$, as desired. □

We now prove by induction that, for $1 \le r \le 100$, it is possible to perform a series of good moves on the first $r$ rooms of $\mathcal{B}$ so that
(a) the numbers of students in these rooms lie in a range $[A, B]$, where $0 \le A \le 20 < 21 \le B$, and
(b) each integer in $[A, B]$ is represented exactly once, with the following two exceptions: Some number $H$ in $[A, B]$, which we call the *hole*, does not appear, and if $A=0$, then $0$ may occur an unlimited number of times.

For the base case $r=1$, we already have such a state with $A=20, B=H=21$. To induct from $r-1$ to $r$ rooms, let $c$ be the number of students in the added room (so $c=20$ or $c=21$). If $c=H$, no moves are necessary; we may simply increase $B$ by $1$ and set $H$ to the new value of $B$. Otherwise, apply Lemma 1 with
$$a = \begin{cases} H+1 & H < c \\ \max\{A, 1\} & \text{otherwise,} \end{cases} \qquad b = \begin{cases} H-1 & H > c \\ B & \text{otherwise,} \end{cases} \qquad \text{and } c=c.$$
This yields a configuration of the desired type with $H=d=a+b-c$ and the range $[A, B]$ possibly expanded on one or both sides, completing the induction. It is easy to check that $\mathcal{M}$ is the only placement of all $2010$ students into $100$ rooms satisfying properties (a) and (b), so the final configuration in our induction is in fact $\mathcal{M}$.

*Step 4:* We now claim that it takes at most $m_2 = 41317$ steps to change $\mathcal{M}$ to $\mathcal{E}$. For a configuration $(a_1, a_2, \dots, a_{100})$, we consider the function
$$g(a_1, a_2, \dots, a_{100}) = \sum_{1 \le i < j \le 100} |a_i - a_j|.$$
Note that if a student walks from $c_i$ to $c_j$, then $|a_i - a_j|$ increases by $2$. Furthermore, if $a_k > \max\{a_i, a_j\}$ or $a_k < \min\{a_i, a_j\}$, then the sum $|a_k - a_i| + |a_k - a_j|$ remains unchanged. On the other hand, if $\min\{a_i, a_j\} \le a_k \le \max\{a_i, a_j\}$, then the sum $|a_k - a_i| + |a_k - a_j|$ increases by $2$. Therefore, on each move, the value of $g$ increases by at least $2$. We may compute $g(\mathcal{E}) = 2010 \cdot 99 = 198990$ and
$$\begin{align*} g(\mathcal{M}) &= 38 \cdot (1+2+\cdots+63-6) + (1+\cdots+62) + (1+\cdots+61) + \cdots + (1+2) + 1 \\ &\quad -(5+4+3+2+1+1+2+\cdots+57) \\ &= 38 \cdot 2010 + \frac{1^2+2^2+\cdots+62^2}{2} + \frac{1+2+\cdots+62}{2} - \frac{5 \cdot 6 + 57 \cdot 58}{2} = 116356. \end{align*}$$
Thus, it can take at most $m_2 = (198990 - 116356)/2 = 82634/2 = 41317$ steps to change $\mathcal{M}$ to $\mathcal{E}$.

*Step 5:* We show that this upper bound $m_2$ can be achieved. Indeed, if we are at a configuration $(a_1, \dots, a_{100})$ with $0 = a_1 = \dots = a_i < a_{i+1} < a_{i+2} < \dots < a_{100}$ (configuration $\mathcal{M}$ satisfies this condition), we can perform the following *wave* of moves to obtain a similar configuration with one less student in $c_{i+1}$ and one more student in room $c_{100}$:
$$\begin{array}{rcl} & \underbrace{(0, \dots, 0, a_{i+1}, a_{i+2}, \dots, a_{100})}_{i \text{ 0's}} & \\ \rightarrow & \underbrace{(0, \dots, 0, a_{i+1}-1, a_{i+2}+1, a_{i+2}, \dots, a_{100})}_{i \text{ 0's}} & \\ \rightarrow & \underbrace{(0, \dots, 0, a_{i+1}-1, a_{i+2}, a_{i+3}+1, a_{i+4}, \dots, a_{100})}_{i \text{ 0's}} & \\ \rightarrow & \underbrace{(0, \dots, 0, a_{i+1}-1, a_{i+2}, a_{i+3}, a_{i+4}+1, a_{i+5}, \dots, a_{100})}_{i \text{ 0's}} & \\ \rightarrow & \dots & \\ \rightarrow & \underbrace{(0, \dots, 0, a_{i+1}-1, a_{i+2}, a_{i+3}, \dots, a_{100}+1)}_{i \text{ 0's}} & \end{array}$$
Because of the assumption that $a_i < a_{i+1} < a_{i+2} < \dots < a_{100}$, it is easy to see that the value of $g$ increases by exactly $2$ during each step in the wave. From configuration $\mathcal{M}$, we can perform a sequence of waves to reach configuration $\mathcal{E}$; that is, we can take exactly $m_2 = 41317$ steps from $\mathcal{M}$ to $\mathcal{E}$.

*Step 6:* We claim now that for every sequence of moves with maximum length from $\mathcal{B}$ to $\mathcal{E}$, there is another sequence of moves of the same length which achieves configuration $\mathcal{M}$ along the way. Let $S$ be the sequence of moves of maximal length from $\mathcal{B}$ to $\mathcal{E}$ which we have just constructed; in particular, note that $S$ consists of good moves from $\mathcal{B}$ to $\mathcal{M}$. Let $S'$ be any other maximal sequence of moves.

We claim by induction on $k$ that there exists a sequence $S''$ of moves from $\mathcal{B}$ to $\mathcal{E}$ with the same length as $S'$ so that the first $k$ moves of $S''$ and $S$ agree for $0 \le k \le m_1$, where we recall that $S$ began with $m_1$ good moves. The base case $k=0$ is vacuous. For the inductive step, we may assume by the inductive hypothesis that $S'$ and $S$ agree on the first $k$ moves. Because $k < m_1$, the $(k+1)^{\text{st}}$ move of $S$ is good; suppose that it acts on two rooms $c$ and $c'$ with $s$ students. Observe that $S'$ must contain some first move $m$ after the first $k$ moves involving either $c$ or $c'$. Without loss of generality, suppose that it involves $c$. If $m$ is not a move between two rooms with $s$ students, we claim that we may lengthen $S'$ by adding such a move, contradicting the maximality of $S'$. There are two cases.

* *Case 1:* A student leaves $c$. If a student leaves $c$ for a room $c''$ with more than $s$ students, we may extend $S'$ by having him instead take the path $c \rightarrow c' \rightarrow c''$.
* *Case 2:* A student enters $c$. If a student enters $c$ from a room $c''$ with less than $s$ students, we may extend $S'$ by instead having a different student move from $c'$ to $c$ and having the student move from $c''$ to $c'$.

Therefore $m$ must involve $c$ and some other room $c''$ with $s$ students. Now, construct $S''$ by removing $m$, inserting it as the $(k+1)^{\text{st}}$ move, and, in all moves after $m$, exchanging the roles of $c'$ and $c''$. This yields a valid sequence of moves because $c'$ does not play a role in any moves after the $k^{\text{th}}$ move and before the original position of $m$. The resulting sequence of moves $S''$ has the same length as $S'$ and matches the first $k+1$ moves of $S$, completing the induction. Thus, we may rearrange the moves of $S'$ so that the first $m_1$ agree with the first $m_1$ moves of $S$, producing a maximal sequence of moves which passes through $\mathcal{M}$.

We conclude that all sequences of moves from $\mathcal{B}$ to $\mathcal{E}$ of maximal length have $M = m_1 + m_2 = 22449 + 41317 = 63766$ moves. By Step 2, this shows that the maximum value of $M$ is $63766$.