The birthday candle problem

After a 1.5-month epic journey1, I am finally settling into my new position at Hendrix College. Here’s a fun problem I just heard from my new colleage Mark Goadrich:

A birthday cake has n lit candles. At each step you pick a number 1 \leq k \leq n uniformly at random and blow out k candles. If any candles remain lit, the process repeats (using a new value of n). As a function of n, what is the expected number of rounds needed to blow out all the candles?

For example, suppose the cake starts out with 14 lit candles. You roll a fair 14-sided die2 to choose a number between 1 and 14. Suppose you roll a 6. You then blow out 6 candles, leaving 8 lit candles. You now roll a fair 8-sided die; suppose you roll a 3. You blow out 3 candles, leaving 5. So you roll a fair 5-sided die. Maybe this time you actually roll a 5, so you blow out all the remaining candles and you are done. In this particular case, the whole process took three rounds; the question is to determine how many rounds it will take on average.

If one starts with n lit candles, it seems clear that the average number of rounds will be less than n (it would be very unlucky to roll a 1 every single time) but greater than 1 (it is pretty lucky to roll an n on the first try, although not nearly as much so as rolling all 1’s).

Have fun thinking about it. There is, in fact, a nice analytical solution, which I will explain in a future post!

  1. US states visited: 9 (Massachusetts, Vermont, New York, Michigan, Wisconsin, Iowa, Kansas, Missouri, Arkansas); countries visited: 4 (US, Canada, Netherlands, Germany); plane flights: 10; hours of driving: 40; beds: 13; unexpected two-week detours to stay with in-laws: 1; number of days late by which the moving company delivered our belongings: 25.

  2. You can make a fair 2n-sided die for any n \geq 3 out of a bipyramid with an n-gonal base.

About Brent

Associate Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.
This entry was posted in challenges, combinatorics, probability and tagged , , , . Bookmark the permalink.

5 Responses to The birthday candle problem

  1. Jamie Hope says:

    Neat, it’s the nth harmonic number. If this comment form had a “preview” button, I would be tempted to sketch out a proof; I don’t trust my LaTeX skills to get it right on the first try. Anyway you promised to follow up with an explanation. 🙂

  2. Maya Quinn says:

    This is an interesting problem. Thinking recursively and collecting terms leads me to guess a sum of harmonic numbers, e.g., take something like ‘digamma(n+1) + gamma’ for n candles. So, for example, my guess for 4 candles would be digamma(5) + gamma = 25/12.

  3. Curtis Bechtel says:

    That’s so funny, I had imagined this exact same problem (with a different scenario – not birthday candles) just a couple weeks ago. I figured that it could be calculated by summing the first n harmonic numbers. Looking forward to your explanation!

  4. elirose says:

    I loved this problem! It has so many layers (like a cake???) — you do one kind of thing just to get to the conjecture, then another entirely different thing to prove it. I wrote up my solution at

  5. Pingback: The birthday candle problem: solution | The Math Less Traveled

Comments are closed.