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

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