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.

Advertisements

About Brent

Assistant 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 http://reallyeli.com/the-birthday-candle-problem-terse.html.

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

Comments are closed.