Skip to main content

Candy Game - Math Puzzle

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

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.


  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).

    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!

    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.

  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.

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

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

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


Post a Comment

Popular posts from this blog

Asking a girl out

This is not a puzzle. So, for those of you who follow this puzzle blog, please bear with me for just one post. Interesting Math in this article though :P

Most of my friends already read an article that I wrote more than an year back - "Speak Up"

Here, inspired by the movie, The Beautiful Mind, I give a mathematical analysis of asking a girl out. Nice time it is. Feb 10. No plans for Feb 14 and I am sure this article makes me look even more geekier and all the more reason for me to believe that I will be alone, yet again. But what the hell, lets do it!

Note: This is not an independent analysis. There are many "mathematics sites" which does "similar" analysis.

@Consultants, correct me if I am wrong in my estimates. :P

Why is there a need to be selective?

From the age of 15, I guess there are approximately 3,600 girls I have liked (On average days, I don't see new girls. But going outside, I like about 30 girls. Saying that I go out once every week right …

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.

(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)

f(0,0) = 1/4[f(…

Fraction Brainteaser

Sent to me by Gaurav Sinha

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?