## Puzzle #174: Happy Birthday!

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!
This entry was posted in Puzzles and tagged , . Bookmark the permalink.

### 6 Responses to Puzzle #174: Happy Birthday!

1. Abhinav Jain says:

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.

2. Pratik Poddar says:

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

3. Prakhar says:

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

• Alok Goyal says:

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

4. Praneeth says:

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