Oh..The answer is 63756.The answer is 3 pages long.I cannot post them.

Hi, does anyone have a solution to this problem? Thanks in advance.

Brief outline of my solution: We consider the reverse process instead, so at the start 2010 students are in 1 classroom. Easy to see WLOG that we can rearrange the 100 classrooms to have decreasing number of students throughout the process, with room 1 having most students. Then use the idea of "swapping moves". Consider the process $M$ with the maximum number of moves, and suppose at some time $t$ during $M$ we have the number of students in each classroom as $(a_1, a_2, ..., a_i, a_{i+1}, ..., a_{100})$ with $a_1\ge a_2 ... \ge a_{100}$ and $a_i \ge a_{i+1}+2$. Claim: there exists another process $M'$ with the same number of moves as $M$, and performs the following move at time $t$: 1 student moves from room $i$ to room $i+1$. This can be proven easily: by maximality of $M$ we know a student must eventually move from room $i$ to $i+1$ (if let's say a student goes from room $x<i$ to room $y\ge i+1$ then the sequence of moves $i \rightarrow y, x \rightarrow i$ is more optimal). Then just swop the moves such that move $i \rightarrow i+1$ happens first and the resulting process will still work. This means we can pick any move we like as long as they satisfy the above condition. We can easily get from the initial $(2010,0,...)$ to $(62,61,...,58,57,57,56,...,1,0,0...)$. Now use the monovariant $\sum a_i^2$ and since it must decrease by at least 2 each move, we have an upper bound on the max number of moves. This upper bound can be reached by repeatedly applying the sequence of moves $(q,q-2)\rightarrow (q-1,q-1), (q-1,q-3)\rightarrow (q-2,q-2), ..., (r+2,r)\rightarrow (r+1,r+1)$ (here $q$ and $r$ are the number of students in room 1 and room 100 respectively, and $(q,q-2)\rightarrow (q-1,q-1)$ denotes a student from a room with $q$ people moves to another room with $q-2$ people) which is always possible now since difference in number of students in consecutive classrooms is at most 1. After some calculations you should get $M=63756$.

Can anyone please elaborate more? I don't understand how the answer ( $M=63756$ ) is obtained. (Sorry for the revive)

jsphkn wrote: This means we can pick any move we like as long as they satisfy the above condition. We can easily get from the initial $(2010,0,...)$ to $(62,61,...,58,57,57,56,...,1,0,0...)$. Now use the monovariant $\sum a_i^2$ and since it must decrease by at least 2 each move, we have an upper bound on the max number of moves. This upper bound can be reached by repeatedly applying the sequence of moves $(q,q-2)\rightarrow (q-1,q-1), (q-1,q-3)\rightarrow (q-2,q-2), ..., (r+2,r)\rightarrow (r+1,r+1)$ (here $q$ and $r$ are the number of students in room 1 and room 100 respectively, and $(q,q-2)\rightarrow (q-1,q-1)$ denotes a student from a room with $q$ people moves to another room with $q-2$ people) which is always possible now since difference in number of students in consecutive classrooms is at most 1. After some calculations you should get $M=63756$. Sorry for bumping, but I do not understand why $(2010,0,...)$ must go to $(62,61,...,58,57,57,56,...,1,0,0...)$ exactly. Could there possibly by multiple 62's, for example? Since then, this could possibly prevent the algorithm $(q,q-2)\rightarrow (q-1,q-1), (q-1,q-3)\rightarrow (q-2,q-2), ...$ from working perfectly. Thank you!

MathPanda1 wrote: jsphkn wrote: This means we can pick any move we like as long as they satisfy the above condition. We can easily get from the initial $(2010,0,...)$ to $(62,61,...,58,57,57,56,...,1,0,0...)$. Now use the monovariant $\sum a_i^2$ and since it must decrease by at least 2 each move, we have an upper bound on the max number of moves. This upper bound can be reached by repeatedly applying the sequence of moves $(q,q-2)\rightarrow (q-1,q-1), (q-1,q-3)\rightarrow (q-2,q-2), ..., (r+2,r)\rightarrow (r+1,r+1)$ (here $q$ and $r$ are the number of students in room 1 and room 100 respectively, and $(q,q-2)\rightarrow (q-1,q-1)$ denotes a student from a room with $q$ people moves to another room with $q-2$ people) which is always possible now since difference in number of students in consecutive classrooms is at most 1. After some calculations you should get $M=63756$. Sorry for bumping, but I do not understand why $(2010,0,...)$ must go to $(62,61,...,58,57,57,56,...,1,0,0...)$ exactly. Could there possibly by multiple 62's, for example? Since then, this could possibly prevent the algorithm $(q,q-2)\rightarrow (q-1,q-1), (q-1,q-3)\rightarrow (q-2,q-2), ...$ from working perfectly. Thank you! If there are multiple rooms with, say, $n$ people, then someone from there would find a room with $n-k$ people where $k$ is greater than or equal to two. It would be most efficient if $k$ is as small as it can be. Sorry if this isn't clear.

The answer is 63756. Let $x_i$ be the number of students in classroom $i$, and we perform the reverse operation. Set $x_i$ such that they would be forever sorted in nonincreasing order. We describe the process in two phases: Phase 1: $(x_i,x_{i+1})\rightarrow (x_i-1, x_{i+1}+1)$ Phase 2: when $x_i-x_j=2, (x_i,x_j)\rightarrow (x_i-1, x_j+1)$. We describe phase 1 in more detail. If there exists $i$ such that $x_i-x_{i+1}\ge 2, (x_{i+1}\ne 0)$, then take the largest such $i$ and we toggle $(x_i,x_{i+1})$. Otherwise, we open up a new classroom. I claim before we open up a new classroom, there exist at most one $i$ such that $x_i=x_{i+1}$. For all other $i$, $x_i-x_{i+1}=1$ if $x_{i+1}>0$. We can actually "merge" those moves: suppose before we open up a new classroom $x_j$, we have $x_i=x_{i+1}$, then we toggle $x_{i+1}$ with that new classroom, such that $(x_{i+1},x_j)\rightarrow (x_{i+1}-1,x_j)$. This is really just toggling $(x_{j-1},x_j), (x_{j-2},x_{j-1}), \cdots, (x_{i+1}, x_{i+2})$, which is valid since in this point, those numbers are consecutive. If $x_i=x_{i+1}+1$ for all $i$ we just toggle $x_1$. We do this until we can't do anymore, and this clearly guarantees $x_i-x_{i+1}<2$ in the end and at most one equal pair. Therefore, the position would end with $x_i=63-i$ if $1\le i\le 6$ and $x_i=64-i$ if $i\ge 7$. Note $(x_i,x_{i+1})$ is toggled $\sum\limits_{j\ge i+1} x_i$ times, so the total number of toggles is $\sum\limits_{i=2}^{63} (i-1)x_i = \sum\limits_{i=2}^6 (i-1)(63-i) + \sum\limits_{i=7}^{63} (i-1)(64-i) = \sum\limits_{i=1}^5 i(62-i) + \sum\limits_{i=6}^{62} i(63-i) = 31\cdot 5\cdot 6 + 63\cdot \frac{68\cdot 57}{2} - \frac{62\cdot 63\cdot 125}{6} = 41649$ moves. Phase 2: Note the current sum of squares of $x_i$ is $57^2 + \frac{63\cdot 62\cdot 125}{6}=84624$. Every such toggle decreases $\sum x_i^2$ by at least two. In the end, the sum of squares is $20^2\cdot 90 + 21^2\cdot 10 $, so this takes $84624-36000-4410=48624-4410=44214$. Dividing by 2 yields $22107$. Adding them up gives $63756$. Phase 2 is obviously optimal. It is achievable, by repeatedly toggling the largest number $m$ and the smallest number with the same parity as that $m-2k$. This is valid since this is really a combination of toggling $(m,m-2), (m-2,m-4), \cdots$, and the range of the $x_i$'s are always consecutive/continuous. It remains to show phase 1 is optimal. We can think of the operation this way: Let $d_i=21$ if $i\le 10$ and $20$ otherwise. Let $s_i=\sum\limits_{j=i}^{100} d_j$. We can think of each toggle $(x_i,x_j)$ as toggling $(x_i,x_{i+1}), (x_{i+1},x_{i+2}), \cdots, (x_{j-1},x_j)$, or a continuous set of unit toggles. In the end, $(x_i,x_{i+1})$ is toggled $s_{i+1}$ times. Therefore, I should toggle $(x_i,x_{i+1})$ as many times as possible.