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.

Comments

  1. JDGM9:03 PM, April 25, 2013

    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. Pratik Poddar5:08 PM, May 20, 2013

      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. Rishav Shandilya5:10 PM, May 10, 2013

    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. Pratik Poddar5:06 PM, May 20, 2013

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

      Delete
    2. Unknown1:07 PM, November 18, 2014

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

      Delete
  3. Puneet Thakkar1:30 PM, July 11, 2013

    Pratik, Have you tried maths puzzle game "Oojle" ??

    ReplyDelete

Post a Comment

Popular posts from this blog

Buying Dimsums

Source: Alok Goyal (Stellaris VP, Ex-Helion VC) puzzle blog Problem: A fast food restaurant sells dimsums in boxes of 7 and 3. What’s the greatest number of dimsums a person cannot buy. Generalize it for p and q where p and q are relatively prime. I loved the puzzle. Hope you enjoy it too.
Read more

Fraction Brainteaser

Source: Sent to me by Gaurav Sinha Problem: Siddhant writes a Maths test and correctly answers 5 out of 6 Arithmetic questions and 20 out of 28 Geometry questions.  In total, Siddhant scores 25 out of 34.  Vaibhav writes another Maths test and correctly answers 20 out of 25 Arithmetic questions and 6 out of 9 Geometry questions. in total, Vaibhav scores 26 out of 34. Note that a) Vaibhav scores more than Siddhant b) Siddhant score better than Vaibhav in both individual topics -  5/6 > 20/25 and 20/28 > 6/9 How is it possible? 
Read more

Consecutive Heads

Let's say A keep tossing a fair coin, until he get 2 consecutive heads, define X to be the number of tosses for this process; B keep tossing another fair coin, until he get 3 consecutive heads, define Y to be the number of the tosses for this process. 1) Calculate P{X>Y} 2) What's the expected value of X 3) What's the expected value of Y This is probably the hardest puzzle I have ever put on my blog. Hence, I will post its solution in the post directly rather than on comment. Solution: 1) (Solved by me finally after 13 months :)) Make a state diagram. Let the state be (a,b) where a is the number of consecutive heads streak "A" is on currently and b is the number of consecutive heads streak "B" is on currently. So, (0,3) (1,3) are final accepted states and (2,0) (2,1) (2,2) (2,3) are failure states. If you get tails, your contribution to the state reaches to "0" f(State) = P(X>Y | "State" configuration initially) ...
Read more