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 re: Forced Equality (Possible Spoiler) by Steve Herman)

At the start, all students(i) have an positive even number of candies or (ii) at least one has 0 candies.

Assume the former, and let the number of candies held by the student(s) with the least be 2x. Of this 2x, the student, say Ady, places x to one side, and passes x, receiving at least x in return. And so on and so on. Eventually, at least the first x must come back to Ady, probably dirty and sticky from being passed around so much. Meanwhile, Ady has never had to touch the second x, since he's always had at least that many handed-on candies to pass on himself.

So let's just take away all of Ady's candies at the start, and to be fair, take away the same amount of everyone else's, calling them, say, 'matched candies'. Now we have case (ii). If everyone else has more candies than Ady, then everyone will end up with at least 1 after passing, which the teacher could round up to 2, but why bother, because she is immediately going to take those 2 candies away from every student, as she did with Ady's earlier, since they are also 'matched candies'.

Repeat this process until, sooner or later, 2 or more adjacent students are without candies. But it makes no difference because the first candiless student receives at least 1, to which the teacher adds another, then on the next round he passes one of these onto the next candiless student and so on until all students have at least 1.

Then the teacher swoops again to remove all the 'matched candies'. Finally a situation is reached where all students have zero candies and the teacher, while consuming all the candies, explains to them that they have just learnt an important lesson about life.

QED

Edited on July 30, 2012, 2:12 pm

Posted by broll on 2012-07-30 14:03:06