The birthday candle problem

After a 1.5-month epic journey¹, 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 die² 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!

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

View all posts by Brent →

5 Responses to The birthday candle problem

Jamie Hope says:

August 7, 2015 at 6:14 pm

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. 🙂
Maya Quinn says:

August 7, 2015 at 11:36 pm

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.
Curtis Bechtel says:

August 21, 2015 at 11:17 am

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!
elirose says:

August 22, 2015 at 11:50 pm

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.
Pingback: The birthday candle problem: solution | The Math Less Traveled

Comments are closed.