This is a very nice puzzle from fivethirtyeight.com (thanks to Suman Saraf for pointing this site to me).

It’s your 30th birthday, and your friends got you a cake with 30 lit candles. You try to blow them out, but each time you blow you successfully extinguish a random number of candles, between one and the number that remain lit. How many blows will it take, on average, to extinguish them all?

As always, please send your answers as comments within the blog (preferred), or send an e-mail to alokgoyal_2001@yahoo.com. Please do share the puzzle with others if you like, and please also send puzzles that you have come across that you think I can share in this blog.

Happy birthday!

### Like this:

Like Loading...

*Related*

I did it inductively by taking small cases and then you can generalise it.The general formula is

F(n)=1+1/2+1/3……..+1/n. We have to evaluate at n=30. The sum can be estimated using integration and it comes close to 4.

Let the expected number of blows for n candles be E(n)

E(0) = 0

E(1) = 1

By linearity of expectation, E(2) = 1/2*(1+E(1))+1/2*(1+E(0))

E(2) = 3/2

E(3) = 1/3*(1+E(2)+1+E(1)+1+E(0)) = 11/6

E(n) = 1/n(n+E(0)+E(1)+….E(n-1)) = 1 + 1/n*(E(0)+E(1)+….E(n-1))

n*(E(n)-1)=E(0)+E(1)+….E(n-1)

(n-1)*(E(n-1)-1)=E(0)+E(1)+….E(n-2)

n*E(n)-n-(n-1)*(E(n-1))+n-1=E(n-1)

n*E(n)-1-n*(E(n-1))=0

E(n)=E(n-1)+1/n

E(n)=sigma (1/i) i varies from 1 to n

Alok – I am sharing my son’s response which is likely wrong. In the first attempt, he blows all thirty which is attempt 1. Or he blows 15 leaving the remaining 15 and he blows 15/2 or 7 in attempt 2. Then he blows 4 out of 8 in attempt 3. In attempt 4, he blows 2 more. Attempt 5 he blows one more and lastly he blows them all in the 6th attempt. So his answer was 6

Prakhar, very nice attempt by your daughter. this problem is best solved by induction. Please see the solution I am posting soon.

Let P(n) be the expected number of trials to lit of n candles:-

so P(1) = 1 and P(2) = 1/2*(1+P(1))+1/2 , Now by generalizing

P(n) = 1/n(1+P(n-1)+1+P(n-2)……+1+P(1))+1/n

= 1/n(P(n-1)+P(n-2)+P(n-3)+….+P(1))+1