A number of students sit in a circle while their teacher gives each student an even number of candies.
When the teacher blows a whistle, each student simultaneously gives half of his or her own candies to the neighbor on the right.
Any student who ends up with an odd number of pieces of candy gets one more piece from the teacher.
Show that no matter how many pieces of candy each student has at the beginning, after a finite number of iterations of this transformation all students have the same number of pieces.
(In reply to
Forced Equality (Possible Spoiler) by Syzygy)
I think that Syzygy has great insights, and is on the right track, but a few more observations need to be made before this is proved. Here is a reworked proof.
Consider A passing to B, and their relative holdings right before the pass. After the pass, B has either the average of their holdings before the pass, or the average + 1. This means that:
1) If A has the same amount as B before the pass, than B's holdings after the pass are unchanged.
2) If A has more than B before the pass, than B's holdings increase, but cannot exceed A's holdings before the pass, even if B gets an extra candy.
3) If A has less than B before the pass, than B's holdings decrease or stay the same, but must wind up exceeding A's holdings before the pass.
And this means that:
a) Whatever value constitutes "the most" cannot increase as a result of a pass. Not only can the students who have "the most" not increase their holding as the result of a pass (as Syzygy pointed out), but no other student can wind up after the pass with more than "the most" before the pass.
b) On any given iteration before we have reached the all-equal "steady state"", the number of students who have the specific "Least" amount must decrease, because at least one of them must receive a pass from somebody who has more than they do. If the number of students who have that specific "least" amount decrease to 0, then we have a new, higher, "least" amount.
c) Therefore, if there are n students, the smallest holding among the group must increase by at least 2 after at least (n-1) passes, and the largest holding among the group can never increase, so eventually the smallest and the largest holding must be equal.
Interesting enough, this is not true without the "extra candy". For instance, if we start with one candy and 3 students, and pass fractional candies around, then we never achieve the situation where each student has 1/3 of a candy. The lowest holding increases asympotically but never reaches (1/3). This is clear, because it is necessarily a rational number whose denominator is a power of 2.
Edited on July 30, 2012, 1:07 pm
re: Forced Equality (Possible Spoiler)
