Brain Teasers
Apartment Block Fire
Dave, the janitor of an apartment block, notices that the boiler pressure is rising, and will shortly explode.
He phones two of the residents, tells them the news, asks them to do the same and phone just two more people, and then get out of the building.
Assume that each of the residents is in, and answers the phone immediately.
If each phone call takes 30 seconds, and it takes each person 90 seconds to get out of the building, how long will it take to empty all 375 apartments?
He phones two of the residents, tells them the news, asks them to do the same and phone just two more people, and then get out of the building.
Assume that each of the residents is in, and answers the phone immediately.
If each phone call takes 30 seconds, and it takes each person 90 seconds to get out of the building, how long will it take to empty all 375 apartments?
Hint
Fibonacci might have the answer!Answer
7 minutes.In the first 30 seconds, Dave rings one other person, call him A.
In the second 30 seconds, Dave rings B, and leaves the building. A rings C.
3rd: A rings D, and leaves. B and C ring E and F.
4th: B and C ring G and H. D, E and F ring I, J, K.
5th: D, E, F ring L, M, N. G, H, I, J, K ring O, P, Q, R, S.
The number of residents informed in each time period is as follows:
1, 2, 3, 5, 8, ...
These are known as Fibonacci Numbers, where each number is the sum of the preceding two.
The total number of people informed is:
1, 3, 6, 11, 19, ...
Each number is the sum of the previous two, plus 2.
Continuing this series we get:
32, 53, 87, 142, 231, 375.
Thus 375 people were informed after 11 periods of phone calls.
11 calls at 30 seconds each = 5.5 minutes, plus 90 seconds for the last people to exit the building gives 7 minutes.
Hide Hint Show Hint Hide Answer Show Answer
What Next?
View a Similar Brain Teaser...
If you become a registered user you can vote on this brain teaser, keep track of which ones you have seen, and even make your own.
Solve a Puzzle
Comments
A classic application of the Fibonacci sequence; good choice!
A nice twist, summing the Fibonnacci series with a constant. Great puzzle!
Yes, I have to agree
Good use of Fibonacci, but how does each person know who to call? i.e. What if B called A (A would be on the phone), or Z called A (A would be long gone)?
doesn't look right...
shouldn't it be:
Dave
/ \
A B 2
/ \ / \
C D E F 4
/\ /\ /\ /\
G H I J K L M N 8
... and so forth...
so on the completion of the 7th step, 222 (2+4+8+16+32+64+12 people were informed. furthermore, during the 8th step, after 128 people made their first call, a total of 350 (222+12 people are already notified, hence only 25 phone calls are needed to complete the total of 375.
At 30 second per call or 1 minute per step, 8 x 1min = 8 mins + 90 secs = 9 1/2 minutes.
I humbly stand corrected.
shouldn't it be:
Dave
/ \
A B 2
/ \ / \
C D E F 4
/\ /\ /\ /\
G H I J K L M N 8
... and so forth...
so on the completion of the 7th step, 222 (2+4+8+16+32+64+12 people were informed. furthermore, during the 8th step, after 128 people made their first call, a total of 350 (222+12 people are already notified, hence only 25 phone calls are needed to complete the total of 375.
At 30 second per call or 1 minute per step, 8 x 1min = 8 mins + 90 secs = 9 1/2 minutes.
I humbly stand corrected.
I made the same error as jvs13. I computed the slowest chain of a binary tree, but this is wrong. The teaser is correct, and a very nice one at that. I don't miss many of these. Good job!
I did have the same quibble with the unrealistic perfect call sequence. It would have been good to provide a rationale, such as the call sequence was predetermined by the emergency evacuation plan.
I did have the same quibble with the unrealistic perfect call sequence. It would have been good to provide a rationale, such as the call sequence was predetermined by the emergency evacuation plan.
This is a fantastic problem.
The key is to note at each 30 second mark, the people who were informed 30 seconds ago and people who were informed 60 seconds ago will inform a new person. Hence, we think of the fibonacci sequence.
Since we're interested in the sum of a fibonacci sequence, it's handy to know the sum of the first n fibonacci terms = the (n+2)th term - 1, which is easily proved by induction.
Because the fibonacci sequence here omits the first two terms (0 and 1), we correct the formula by subtracting 2 instead of 1.
After listing the fibonaccis up to 377. We can see it takes 11 calls to inform everybody. Hence, the total time spent in seconds is 11 * 30 + 90 = 7 minutes.
Thank you very much for the problem.
The key is to note at each 30 second mark, the people who were informed 30 seconds ago and people who were informed 60 seconds ago will inform a new person. Hence, we think of the fibonacci sequence.
Since we're interested in the sum of a fibonacci sequence, it's handy to know the sum of the first n fibonacci terms = the (n+2)th term - 1, which is easily proved by induction.
Because the fibonacci sequence here omits the first two terms (0 and 1), we correct the formula by subtracting 2 instead of 1.
After listing the fibonaccis up to 377. We can see it takes 11 calls to inform everybody. Hence, the total time spent in seconds is 11 * 30 + 90 = 7 minutes.
Thank you very much for the problem.
Mar 07, 2011
Am i misunderstanding the question. He says the first guy calls 2 ppl and asks the 2ppl he called to ring 2 other ppl each?
so shouldnt it be 1,2, 4, 8, 16, 32 ppl notified?
so shouldnt it be 1,2, 4, 8, 16, 32 ppl notified?
To post a comment, please create an account and sign in.
Follow Braingle!