Bulb dropping
You need to figure out how high a bulb can fall from a 1000 story building before it breaks. What is the minimum # of bulbs you will ever need for this and what is the largest number of drops you would ever have to do to find the right floor where the bulb would break? Lets say you are given an unlimited supply of the bulbs. But figure out how much you will actually ever need and how many drops you will ever have to make to figure out the right floor. Lets take this a little further - For a 's' story building and 'b' # of bulbs, find the optimal strategy that will minimize (worst case scenario) the number of drops required to determine the floor on which the bulb will break.Level: Medium to Hard
posted by Karthik Nagaraj at
3:09 PM
24 Comments:
Karthik,
I'm going to stay off for some time ..on public demand :) I have already gotten a couple of threats in advance to give others an opportunity to atleast look at the puzzle ..
Happy Puzzling people ! It gives you quite a kick ...atleast tickles those brain cells that have been lazying around since 10th grade..
Cheerz,
-Kala
whats the catch? You only need 1 bulb. Drop it from floor 1. If it doesnt break pick it up and drop it from floor 2 & so on...until it breaks from a praticular floor
Ajit,
The catch is you need to minimize the number of throws as it states in the problem. In your case the # of throws will be 1000. Thats not an optimal solution. So minimize the # of throws and also find out how many bulbs you will need to perform such an optimal solution.
Kala,
At least you can comment on what others write. Pour in your suggestions. Keep participating. Don't lay off for a long time. :)
P.S: The bad king's puzzle is still UNSOLVED !!!
i guess using a binary search would be the fastest way to find the floor. 2^10 = 1024 > 1000, so 10 bulbs need to be dropped.
Vikram,
If you use binary search then calculate how many floors you will really need to test before you can draw the conclusion that the floor is a break floor. Remember we are optimizing the # of bulbs needed and the # of floors that need to be experimented. I'm sorry, but 10 bulbs is not the correct answer. No doubt you can use any # of bulbs to test it in whatever fashion you think is right, BUT we need an optimal solution.
I think you need 32 bulbs and 63 trys. I'm using the convergence series. Am I on the right track?
Can you please explain how you arrived at the figures. Well, there are a couple of solutions to this problem but obviously only one is optimal. Let me put it this way - 63 looks about right for one method of solution. But for that 32 bulbs is not required. Look again. Explain how you got the 63 and you will see for yourself why 32 bulbs is not required.
I think we need 2 bulbs and in max of 100 iteration. devide the number of floors into 100*10 sections and and again devide each esction by 10*10 sections.first go fore 10th flower dropp the bulb ,if the bulb is broken go for next below folwer ,continue the procedure till the bottom of 10th flower.if bulb is not broken in top 10th flower then go for the next 20th flower continue the above mentioned procedure you will get the exact solution tothe problem.
vishwanath (mca 6th sem bit)
Vishwanath,
Welcome! So you need only 2 bulbs, wow - thats correct. But the # of floors to be tested is not right. It is not 100. I didn't quite understand your solution. When you say go to the first 10th floor and drop the bulb, and it breaks, then you say go to the blow floor and keep trying until it breaks. Right? Shouldn;t you try to go upwards once you break the bulb. If you go downwards again then with bulbs, if some 'mth' floor the second bulb breaks, then you will never get to know if from the (m-1)th floor also, the bulb would have broken. Correct me if I'm wrong.
So simplify what you have said - simply divide the 1000 into 100 floors section and keep trying each of the set of the 100. Try every 100th floor starting from the 100th floor itself until you reach some 100th floor section where the first bulb breaks and then start from the previous 100th section + 1th floor until you really find the floor that the second bulb breaks. Then in that case your worst case # of drops will be 10 (100th, 200th, 300th, ...) and then from 901st floor until 999th floor, we need 99 drops with the second bulb -> total of 109 drops. How did you get 100 drops? Can you please explain? Good thinking, the lines of thinking is correct, keep them flowing in...Let me know if what you are thinking is what I have tried to explain. I may have wrongly understood.
or u can use 3 bulbs and test a maximum of 30 times instead of 110
Vikram,
But then the # of bulbs are not optimized. Then idea is to use minimal set of bulbs and test minimum # of floors. Take another crack at it.
Victoria,
This site is open for ALL. Add all you want, comment all you want for all open puzzles. It will be fun if you spread the word around and we have more people interacting and pouring in their viewpoints. Try adding the RSS feeds to your feeder and you will get updates everyday! The RSS feed is available on the top right corner of the home page of the puzzle.
Add a link to your own blog: http://puzzleguru.blogspot.com
Thanks for visiting and dropping by.
this problem is a little like the bad king's wine problem. there has to be a trade off between number of bulbs broken and the number of floors tested.
1 bulb - 1000 drops
2 bulbs - 110 drops
3 bulbs - 30 drops
4 bulbs - 26 drops
5 bulbs - 22 drops
...
8 bulbs - 12 drops
9 bulbs - 11 drops
10 bulbs - 10 drops
"For a 's' story building and 'b' # of bulbs, find the optimal strategy that will minimize (worst case scenario) the number of drops required to determine the floor on which the bulb will break."
for a given number of bulbs 'b' we can find the least number of floors 'c' that need to be tested.
we can fix the optimal strategy to be to minimize the product b*c or a more complex function with b and c. :)
Vikram,
I understand your lines of thinking, BUT I doubt if a similar solution to the king's problem can be applied here. The reason being that if a floor 'm' is the breakage floor, then all floors below it also will result in the breaking of the bulb. So in that case you can never achieve an optimal strategy to minimize the # of bulbs needed and the # of floors that need to be tested. You could arrive at a solution, although it will not be optimal.
Let me give you all a clue in getting to it. Vishwanath got the # of bulbs needed correct. Yes, we need 2 bulbs. Now how will you use the 2 bulbs to determine how many floors need to be tested. All you need is an upper limit in finding which floor the bulb broke and a lower limit at which the bulb did not break with the first bulb. Now use the other bulb to determine between these bounds the correct break floor. Here is what I mean - If you find that the bulb did not break at x and you found that it broke at floor y (y > x) then minimize y-x to get an optimal solution. Hope this can put you onto the right track.
hai karthik this is tejesvi from bit 6th sem m.c.a
U need a total of 109 iterations in worst case to solve this problem or to decide from which floor the bulb breaks.
first divide the 1000 floor into a unit of 100 floors each so that u have 10 units each with 100 floors
each.go to the 100th floor drop the 1st bulb if it breaks then start from the 1st floor,if doesnt then go to 2nd and repeat till the bulb breaks.
Tejasvi,
Nice to have you on board to solve the puzzle. Welcome! Your answer is logically correct. For all you know you could divide it into how many units you want and proceed in your methodology, BUT it is not optimal. Can we do better than testing 109 floors in the worst case? I'm sure you can. But whatever you have written is a good starting point. Start to minimze the floors needed and arrive at a pattern!
so it takes 64 iterations. divide 1000 floors by 25 u get 40 units each of 25 floors.now u go to the 25th floor and drop a bulb if it breaks u go to the 1st floor and if it doesnt go to 2nd floor and so on till it breaks.If it doesnt break at 25th floor u go to the 50th floor and drop if it breaks u come back to 26th floor and start throwing the bulb and so on till 1000 floors.
Tejasvi,
Again I'm inclined to say yes, but there is still a better way. Ok, lets look at it this way - Why did you divide 1000 by 25 to 40 floor blocks? How do you know that something else might now result in a better way. Say if you start at the 32nd floor. Then in the worst case you will drop the bulbs on 32nd, 64th, 96th, ... until the 1000th floor, which gives you about 32 attempts. Now if the bulb breaks on the 1000th floor you have to test the last set - which will give you about 31 attempts. So a total of 63 drops. Not 64!
So what is the methodology to decide which floor to begin at? Its not just some random number. How did we get 32 to begin with? Think about it and you would have cracked a portion of the problem. BUT now if I were to tell you that even 63 is not optimal, then what is the optimal number of throws you need to try? One thing is for sure - it is definitely lesser than 63.
Think about it
Drop from 500th floor.
If it doesn’t break go to floor 750. i.e. (1000+500)/2
If it breaks, go to floor 250. i.e (500+0)/2
Continue this process of narrowing down.
This seems to be an optimal strategy. What are your views?
- Mohit
I Think only one bulb is enough,
using the assumption that when a bulb breaks atleast the bulb peices will fall for one meter.
using this asumption.
one bulb drop it from the 100th floor and come checking down for the glass pieces, where u get the first would be the answer.
Anonymous,
Sorry I didn't quite understand your logic. In all respects, ignore the made assumptions as no information on how the bulb breaks and where the glass peices go by is not available to us. All we know if the bulb breaks or not when we drop it from a floor. We can only go up or down the floor and not to the ground and inspect the actual broken bulb.
Mohit,
I agree that the binary distribution way of choosing the floors is fine BUT how many bulbs do you need? Lets say that the bulb breaks at 500th floor, then another one will break at the 250th floor, then anither one will break at the 375th floor, another one will break at the 438th floor, another one at the 469th, another one at the 485th floor, another one at the 492nd floor, another one at the 496th floor, another one at the 498th floor,
another one at the 499th floor. So That gives it a total of 10 bulbs.
Using this way you tend to use a lot of bulbs to lower the margin of checking the floors. So, I'm afraid the answer is not correct. Vikram has already told the same answer and I had already commented that it is not correct.
Again, somebody here has already said that the # of bulbs that need to be used is 2. So we know that the optimal solution is possible with 2. We also know that the starting point is 63 drops (Tejasvi already solved it to be 64 and I commented that it is 63, not 64, I showed how also). The only thing now is, can we do better than 63? Do we have to test 63 floors?
Ok, this has been open for a week now and thought I would resolve it by posting the solution:
Many people got to the stage of telling that you need 2 bulbs to perform this test and you need to test about 63/64 floors. Well at the first crack to the problem yes, you need 2 bulbs and you need to test 63 floors in the worst case. How did we get that?
Take the square root of 1000 ~ 32
So start from 32nd floor and proceed upwards every 32 floors beyond that until you find an upper limit on the breaking floor. So that way you would need to test 32 floors until you reach the 1000th floor in the worst case. Now you know the limits are 968 and 1000. Start from 969 and proceed till 999. That is about 31 more floors. So a total of 63 floors.
So a generic answer for a 's' story building will be is to take the square root of s and that will give you the starting floor. So # of drops = sqrt(s) + sqrt(s) - 1 = 2*sqrt(s) - 1. Now this is the case when you will ever need only 2 bulbs to perform this test. Lets say you can use b bulbs tp perform the test. Then take the bth root of s to get the starting floor and then proceed further upwards.
Now, comes the jolt: Is 63 really needed? I thought so until I bumped across another reasoning that proved me wrong and this showed another methodology that can be used to get lesser # of floors to be tried out.
The idea in this methodology is to use a differential scheme to determine the next floor to try so as to minimize the # of floors to try as we go upwards. For simplicity lets take 100 floors. According to our previous logic we would get 2 * 10 - 1 = 19 floors need to be tested for the worst case scenario. Now in the new methodology start writing the floor numbers from 100 and keep subtracting series of 0, 1, 2, 3, ...to get lower floor numbers and stop when you can subtract anymore. This is how it will be:
100 - 0 = 100
100 - 1 = 99
99 - 2 = 97
97 - 3 = 94
94 - 4 = 90
90 - 5 = 85
85 - 6 = 79
79 - 7 = 72
72 - 8 = 64
64 - 9 = 55
55 - 10 = 45
45 - 11 = 34
34 - 12 = 22
22 - 13 = 9 -> Stop because 9 - 14 = -5, not correct!
So now we got the floor numbers to try. Observe it carefully, as we proceed upwards, the # of in between floors to test reduces.
So this way, the # of floors that need to be tested are in the worst case (if it is floor 8, floor 21, ...) is 14 and not 19.
Apply similar strategy for the 1000 floor case. Now, one might ask, how to generate this for sequence for higher numbered stories: Simple - write a simple computer program, that will spit out this sequence for you. I have one here in C/C++.
void printFloorsToTest(int s)
{
int step = 0;
printf("Floors to test:\n");
while (s - step > 0)
{
printf("%d\n", s-step);
s = s - step;
step++;
}
}
So, this will apply to any generic 's' story case. In any case you will only need 2 bulbs even out of the 'b' bulbs. To use all the b bulbs, then you would need to reconfigure the solution to suit the b bulb scheme and yet maintaining the optimal # of floors that need to be tested.
This puzzle is now SOLVED!
Subscribe to Post Comments [Atom]
<< Home