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.
Irrespective of the number of candies initially given to the students, we will always have a ‘Most’ number of candies and a ‘Least’ number of candies. We might have more than 1 occurrence each of the 'Most' & 'Least' number.
In any case, after the first iteration, it is impossible that:
1) The student with the ‘Most’ number of candies increases his or her count of candies ... since they would not have received more than they would’ve given away.
2) The student with the ‘Least’ number of candies reduces his or her count of candies ... since they would not have received lesser than they would’ve given away.
Also, in case there is only one occurrence of a ‘Least’ number of candies, it would be eliminated after the next iteration.
Hence, after multiple iterations, the difference between the ‘Least’ & ‘Most number of candies, is bound to decrease ... eventually becoming 0 ... i.e. all students will have the same number of candies.
|
|
Posted by Syzygy
on 2012-07-30 04:37:09 |
Forced Equality (Possible Spoiler)
