A group of children is sitting around a round table . At first, each child has an even number of candies. Each turn, each child gives half of his candies to the child sitting at his right. If, after a turn, a child has an odd number of candies, the teacher gives him\her an extra candy. Show that after a finite number of rounds all children will have the same number of candies.
Problem
Source:
Tags: combinatorics
13.03.2019 17:13
13.03.2019 17:17
Extremal principle. Let a child have $m$ candies and the to his left have $n$ candies. Then this child gets $\frac{m+n}{2}$ candies or one more. Notice that if neither of $m$ and $n$ is largest then $\frac{m+n}{2} +1$ is also less than this largest number. But now let's say that $n$ is the largest. Consider a child with less than $n$ candies with a child to his left who has $n$ candies. If he has $n-2$ candies before the turn(can't be $n-1$ due to parity issues) then we will have $n$ after the turn. Else he has less candies that that. So the maximum number of candies a child has doesn't increase in any turn. Similarly consider minimum. Obviously by the same logic the minimum doesn't decrease. But we need to show something more. Consider some consecutive students who all have the least number of candies. Note that the rightmost child loses this status in a turn while no other child gains the status. So the minimum candies a student has increases or the number of students having minimum number of candies decreases. Combining both results the process must stop. P.S. The disadvantage of using a phone is that you get sniped easily.