Candy distribution problem

Candy distribution problem

There are n students in a circle, each of them start with a[0] ... a[n-1] candies. There is also an infinite pile of candies. Each round, student i checks his candies a[i], if a[i] is odd, then he gets one candy from the pile to make a[i] even, and then pass a[i]/2 to student i+1. Note that student n-1 will pass half of his candies to student 0. The process stops when all students have equal number of candies.

The problem is, does this ever converge, that is, does this process always end in finite steps?

The answer is:














YES.

Proof: W.l.o.g. let student 0 be the one with maximum number of candies. That is, a[0] >= a[i] for i = 0..n-1. Let b[0] = a[0] if a[0] is even, a[0]+1 if a[0] is odd. We claim that no student has more than b[0] candies in the process. This puts a ceiling on the number of candies a student can have. On the other hand, Let amin = a[j] be the minimum candies when students started, then each step, some student with amin candies will have their number of candies strictly greater. An induction will yield that the students will have equal number of candies eventually.