Combinatorics with candies Another problem I couldn't solve:
In a class there are $n$ students. Each of them initially has zero candies. The teacher comes into the class, and chooses 2 students with the same number of candies, let it be $x$.
1) If $x=0$ then he gives one candy to one of the two students.
2) If $x \neq 0$ then he takes one candy from one of the two students, and gives it to the other student.
Eventually, the teacher cannot perform any more moves. Prove that, at this time students must have $0,1,2, \ldots, n-1$ candies at some oder.
 A: I admit it is not an elegant solution, but it should work. Imagine there would be a student Alfred with $n$ candies. To reach this situation, one would first need Alfred to have $n-1$ sweets, since he can only get one per move. To get him to $n$, there would have to be a second student that also has $n-1$ sweets, so he can give one to Alfred. But to get into that situation, this second student also has to have $n-2$ sweets first and get them from somebody. This somebody obviously can't be Alfred as he already must have $n-1$, so there must be a third student with $n-3$ sweets that can give one to the second student.
If we continue this way, there must always be an $i$th student that has $n-i$ sweets so Alfred can reach $n$. As all of them are different, and there are only $n$ students, we must first have a situation where the students have $0,1,2, \dots, n-1$ candies at some order, but then the teacher has no more move. So, we have shown that there can't be anyone with $n$ sweets.
Now, the rest is simple. If the game terminates, every student must have a different amount of candies (otherwise the teacher would still have a move), and since no student has $n$ candies or more, the students must have $0,1, \dots, n-1$ candies in some order, as this is the only possibility how they can all have a different amount.
An open question would still be if the game has to terminate at some point, but that wasn't asked; I'll comment if I know a solution to that.
A: Let $x_i$ be the number of candies possessed by the $i^\text{th}$ student, a quantity which may change from time to time.
Claim 1. The quantity $\sum_{i=1}^nx_i^2$, initially $0$, increases by at least $1$ after each move.
When the teacher hands out a new candy, the sum of squares increases by $1$; when the teacher takes a candy from a student with $x$ candies and gives it to another student with $x$ candies it increases by $2$, as the term $2x^2$ is replaced by $(x-1)^2+(x+1)^2=2x^2+2$.
Claim 2. For each $k\in\{1,\dots,n\}$, the number of students with $\lt k$ candies is always $\ge k$.
Let $P(k)$ denote the statement: at all times there are at least $k$ students who have $\lt k$ candies.
$P(1)$ is true: there is always at least one student with no candies. This is true initially, and every time a student with no candies receives a candy, another student with no candies remains empty-handed.
$P(k)\implies P(k+1)$ if $1\le k\lt n$: Since $k+1\le n$, $P(k+1)$ is true initially; we have to show that it remains true after each move where a student with $k$ candies gains a candy. When that happens, another student with $k$ candies loses a candy; and the number of students with $\lt k$ candies, already $\ge k$ because of $P(k)$, is now $\ge k+1$. Of course, if there are at least $k+1$ students with $\lt k$ candies, there are at least $k+1$ students with $\lt k+1$ candies, so $P(k+1)$ still holds.
By induction, $P(k)$ holds for all $k=1,2,\dots,n$.
Claim 3. The game must end after a finite number of moves.
This is because by Claim 1 the quantity $\sum_{i=1}^nx_i^2$ increases by at least $1$ after each move, while by Claim 2 it is bounded by $\sum_{i=1}^n(i-1)^2=\binom n3+\binom{n+1}3$.
Claim 4. When the game ends, $(x_1,x_2,\dots,x_n)$ is some rearrangement of $(0,1,\dots,n-1)$.
By Claim 2 we always have $x_i\lt n$. When the game ends the numbers are all different (or the teacher could make another move), so they are $n$ distinct numbers in the set $\{0,1,\dots,n-1\}$.
