Log In

Candy game

Posted on: April 23rd, 2013 by
4

A group of students are sitting in a circle with the teacher in the center. They all have an even number of candies (not necessarily equal). When the teacher blows a whistle, each student passes half his candies to the student on his left. Then the students who have an odd number of candies obtain an extra candy from the teacher. Show that after a finite number of whistles, all students have the same number of candies.

via cut-the-knot.org


4 Responses to Candy game

  1. Bharatram had this to say about that:

    At every passing step, the minimum number of candles held in the circle increases at least by 1, and the maximum number of candles decreases at least by one, so after a whistle is blown, the difference between maximum and minimum decreases at least by 2. And correcting for odd candles can at most increase this difference by 1.
    So after every round, the difference between maximum and minimum decreases at least by 1, which means that if the initial difference was k, within k steps all people would have an equal number of candles.

    • Gowtham Kumar had this to say about that:

      Nice :-)

    • Gowtham Kumar had this to say about that:

      Issue with your solution:
      suppose the maximum is 12 and the person to his right has 10 candies. Then, after the whistle, the maximum is ceil((12+10)/2)=12, unchanged.
      Similarly, if minimum is 2 and the person to the right of minimum also has 2, after the iteration he still has 2

    • Gowtham Kumar had this to say about that:

      We edited your solution, but the general idea works. Here are the observations:

      1. The maximum number of candies held by a single student can never increase.
      2. The minimum number of candies held by a single student always strictly increases, unless the student to his right also has the minimum number of candies, in which case the length of the longest consecutive segment of students who have minimum number of candies strictly decreases. Thus eventually the minimum has to strictly increase.
      3. Since the minimum has to strictly increase in a finite number of steps and cannot go beyond the maximum, all the numbers must eventually be equal in atmost n(max-min) steps.


{"result":"error", "message":"You can't access this resource as it requires an 'view' access for the website id = 1."}