Quant, Math & Computer Science Puzzles for Interview Preparation & Brain Teasing
A collection of ~225 Puzzles with Solutions (classified by difficulty and topic)

Apr 24, 2013

Candy Game - Math Puzzle

Source: Mailed to me by Sudeep Kamath (PhD Student, UC at Berkeley, EE IITB Alumnus 2008) - He found it at http://puzzletweeter.com/

Problem:
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.

Update (20 May 2013):
Partial Solution posted by JDGM in comments. Completed by me.

7 comments:

  1. At any time, the size of the largest and smallest piles are upper and lower bounds on pile size for the rest of the game. While the lower and upper bounds are distinct, the lower bound must eventually increase. This persists until upper and lower bounds are equal, and consequently all piles are equal.


    Rigor for the first sentence:
    No largest(smallest) pile in the circle can increase(decrease) in size when the whistle is blown as it will always pass half its candies to the left and receive at most(least) that same number from the right.

    Rigor for the second sentence:
    While the piles are not all equal there will be some smallest pile with a larger pile to its right. This smallest pile will increase in size when the whistle is blown. Consequently either the pile size lower bound will increase, or the number of tied smallest piles will decrease (note it is not possible for a non-smallest pile to join this set of persistent tied smallest piles when the whistle is blown, because it will always retain half its greater-than-lower-bound size and gain at least lower-bound/2). In the repeated case of the latter, eventually there will be one smallest pile which will increase in size on the next whistle blow and hence there will be a new, higher lower bound (not necessarily that pile's new candy-count, however).

    Note:
    It is not necessary for my proof, but helpful in understanding what is going on, to realise that the upper bound can decrease as the game progresses, and that there is no way for candies to be removed from the circle - only added!

    ReplyDelete
    Replies
    1. Thanks for the solution. You did not incorporate the fact that the teacher could add candies in case the number of candies with a student is odd. However, the key idea remains the same.

      Solution from the source:
      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.

      Delete
  2. Let us assume the no. of students be n and each student has even no. of candies.Let it be 2m, 2m+2, 2m+4, 2m+6, 2m+8, 2m+10, 2m+12, 2m+14, 2m+16, 2m+18, 2m+20...and so on.Also,suppose the students are sitting in the clockwise manner.Now,after every whistle a student passes half of his candies to the student on his left and if the student has an odd no. of candies then he gets an extra candy from the teacher.Lets start with the student having 2m candies.He will pass m candies to the student having m+1 candies.This student passes his m+1 candies to the student having 2m+4 candies.So,what is happening with the 2nd student student i.e, who was having 2m+2 candies earlier.He is passing his m+1 candies and receiving m candies.So, the no. of candies he is having after the first whistle is 2m+1.Similarly,the student with 2m+4 candies will have 2m+3 candies after the first whistle and so on.

    Further,2m+1, 2m+3, 2m+5...are all odd integer.So, they will get an extra candy from the teacher.Hence,after the first whistle each student remain with the same no. of candies that they originally had i.e, at the beginning.So,we can say that after a finite whistle they will have equal no of candies.

    ReplyDelete
    Replies
    1. You have read the question wrong. You are not supposed to decide the initial configuration.

      Delete
    2. Right. It needn't increase by a factor of 2.

      Delete
  3. Pratik, Have you tried maths puzzle game "Oojle" ??

    ReplyDelete