It’s his 30th birthday, and his friends got him a cake with 30 lit candles. He tries to blow them out, but each time he blows, he successfully extinguishes a random number of can- dles, between one and the number that remain lit. How many blows will it take, on average, to extinguish them all? (approximate it to the nearest whole number)

Options

A. 3
B. 4
C. 5
D. 6

Explanation

The answer is very close to 4! More precisely, it will take about 3.994987 blows. Why? Let’s start with a smaller number of candles and work our way up. Suppose you have a cake with just a single candle. You’ll blow it out in one blow, for sure. Suppose there are two. Half the time you’ll blow them both out in one go, and half the time it’ll take two blows. Let’s make a list:
One candle: 1 Two candles:` (1//2)​ 1+(1//2)​⋅​2=1.5`
Three candles: `(1//3)​⋅​1+(1//3)​⋅​(1+1.5)+(1//3)​⋅​(1+1)=1.83^(-)`
Four candles: `(1//4)​⋅​1+(1//4)​⋅​(1+1.83^(-))+(1//4)​​(1+1.5)+(1//4)​​(1+1)=2.083^(-)` With each additional candle, you have an equal chance of blowing them out in ne go and of only snuffing some specific number, leaving some to tackle on the next blow. Notice the pattern! For one candle, the average number of blows is one. For two, it’s `1+1//2.` For three, it’s `1+1//2+1//3`. For four, it’s `1+1//2+1//3+1//4.` And so on. So to get the answer, we simply compute this harmonic sum
`sum (1//i),i` goes from i to `30 = ~~3.994987`