- #1
srfriggen
- 307
- 6
Preface: This is a question we are working on in a course called "Problem Solving." I am not looking for an answer, but only some clarity on how to phrase my answer.
The question is as follows: You have a ladder with 100 rungs and two bottles. From some unknown height above a certain rung the bottles will break. Every rung below that you can drop the bottles then pick them up.
We want to find the lowest rung at which the bottles will not break, using only two bottles, and in the least amount of trials.
Strategies discussed: Say you have 100 bottles, you can just climb and drop till one breaks.
But with two bottles we figured that you might go up by 5 rungs, drop a bottle, repeat. When a bottle breaks, (say on the 30th rung) you would go down to the 26th rung and drop from there, up till 29, till one breaks.
We looked at worst case scenarios. If you go up by 5, then the 100th rung would be take the most trials since you drop 20 times to get to 100 (it breaks) then have to check 96, 97, 98 and 99.
You can improve that number by using say 10. Then its 10 drops to 100 (breaks), then check 91 through 99.
But if you go up by 9 then your worst case scenario is actually 99. It can break at 99, then you only have to check 91 through 98.
The number 8 has an even better worst-case scenario: Let's say the break point is 100. Then you would break 96, 100, 97, 98 and 99.
But if the break point was 96 you would have to check 96, 89, 90, 91, 92, 93, 94, 95. So that rung is actually worse, but its the best you can do.
I can't quite phrase my answer. It has something to do with dividing into 100 but leaving a large remainder but also not using a large number. Like 12 multiplies to 96 as well but worst case you have to check 11 more rungs, so its not as good as 8 which has a remainder of 4, and you only have to check a max of 7 rungs. 6 multiplies to 96 too but takes more trials to get there. Any help would be greatly appreciated.
The question is as follows: You have a ladder with 100 rungs and two bottles. From some unknown height above a certain rung the bottles will break. Every rung below that you can drop the bottles then pick them up.
We want to find the lowest rung at which the bottles will not break, using only two bottles, and in the least amount of trials.
Strategies discussed: Say you have 100 bottles, you can just climb and drop till one breaks.
But with two bottles we figured that you might go up by 5 rungs, drop a bottle, repeat. When a bottle breaks, (say on the 30th rung) you would go down to the 26th rung and drop from there, up till 29, till one breaks.
We looked at worst case scenarios. If you go up by 5, then the 100th rung would be take the most trials since you drop 20 times to get to 100 (it breaks) then have to check 96, 97, 98 and 99.
You can improve that number by using say 10. Then its 10 drops to 100 (breaks), then check 91 through 99.
But if you go up by 9 then your worst case scenario is actually 99. It can break at 99, then you only have to check 91 through 98.
The number 8 has an even better worst-case scenario: Let's say the break point is 100. Then you would break 96, 100, 97, 98 and 99.
But if the break point was 96 you would have to check 96, 89, 90, 91, 92, 93, 94, 95. So that rung is actually worse, but its the best you can do.
I can't quite phrase my answer. It has something to do with dividing into 100 but leaving a large remainder but also not using a large number. Like 12 multiplies to 96 as well but worst case you have to check 11 more rungs, so its not as good as 8 which has a remainder of 4, and you only have to check a max of 7 rungs. 6 multiplies to 96 too but takes more trials to get there. Any help would be greatly appreciated.
Last edited by a moderator: