Monday, May 14, 2012
100 Floors to a Building
There is a building with 100 floors. You have two identical balls. You know that there is a floor n, such that if you drop one of the balls you have from this floor it does not break, but if you drop it from any higher floor it breaks.
If one ball breaks, you can use another one.
What is the minimum amount of drops (trials) you have to make at different floors to be sure to find the floor n?
Subscribe to:
Post Comments (Atom)
My logic tells me 6 minimum, but likely 7. I will start at floor 50, and if it breaks, I go to floor 25. If it breaks again, I go to floor 12, or if it doesn't, I go to floor 37, etc. In essence, I go the half of the distance (rounded up) between the last two trials, until I get to floor n. See example below:
ReplyDeleteStart: Floor 50. It breaks.
Go to: Floor 25. It breaks.
Go to: Floor 13. It does not break.
Go to: Floor 19. It does not break.
Go to: Floor 22. It breaks.
Go to: Floor 21. It breaks.
Go to: Floor 20. It does not break.
If it did not break on Floor 21, we will have used 6 trials, but in the example we have used 7. So - I think minimum = 6.
My 1st solution was n+1
ReplyDeleteI have started with step 1, step 2, ..step n(ball won't break), step n+1(it breaks)
but then I minimized it to
(n/2)+1 when n is even
[(n+1)/2] + 1 when n is odd
I have started with even steps : step 2, step 4, step 6.. once found that ball is brking at any step, will chk for a step below it.
oooops... read step as floor *
DeleteI agree with n + 1, you start on 1, drop the ball at each story going up until it breaks, the floor below that will be your n floor.
ReplyDelete14 Drops... Explanation: Drop until one breaks. Then go down to the floor above your previous drop where it didn't break, and start dropping the other ball on the way up to the floor where the first break occurred. You have to count all the previous floors where the test drops didn't break and add them to the group of floors you are analyzing. This requires the number of floor groupings to be decreased as you go to higher floors. Like this:
ReplyDeleteFloor Drop from floors Total number drops
12 1 - 11 12
24 13 - 23 12
36 25 - 35 13
46 37 - 45 13
56 47 - 55 14
65 57 - 64 14
73 66 - 72 14
80 74 - 79 14
86 81 - 85 14
91 87 - 90 14
95 92 - 94 14
98 96 - 97 14
100 99 14
(Jim May)
The email on my answer above jiggled the spacing so that it is hard to read. The headings are:
DeleteFloor(i.e., 12)
Drop from floors(i.e.1-11)
Total number drops(i.e. 12)
I hope this helps
Jim May
The MINIMUM number of tries is de-facto 1 :)
ReplyDeleteThe real answer is probably 50. We have only TWO balls at our disposal. Throw the first one from floor 51. If it breaks go down to floor one and work yourself up with the other ball. If it doesn't break work yourself up to 100.
/HR
Re: Anonymous 5/15/2012 @4:40
ReplyDeleteWhy would you do it in 50 when the solution above shows you can do it in a maximum of 14?
Hm... point taken. I rest my case.
ReplyDelete