## 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?

1. 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:

Start: 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.

2. My 1st solution was n+1

I 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.

1. oooops... read step as floor *

3. I 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.

4. 14 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:
Floor 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)

1. The email on my answer above jiggled the spacing so that it is hard to read. The headings are:
Floor(i.e., 12)
Drop from floors(i.e.1-11)
Total number drops(i.e. 12)
I hope this helps
Jim May

5. The MINIMUM number of tries is de-facto 1 :)

The 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

6. Re: Anonymous 5/15/2012 @4:40
Why would you do it in 50 when the solution above shows you can do it in a maximum of 14?

7. Hm... point taken. I rest my case.

Leave your answer or, if you want to post a question of your own, send me an e-mail. Look in the about section to find my e-mail address. If it's new, I'll post it soon.

Please don't leave spam or 'Awesome blog, come visit mine' messages. I'll delete them soon after.

Enter your Email and join hundreds of others who get their Question of the Day sent right to their mailbox