Find Lowest Rung to Drop Bottles & Prevent Breakage - Problem Solving

[srfriggen]

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.

 

[Alloymouse]

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.

This looks like some sort of problem requiring "balance" between your first trial (going up x steps and dropping until it breaks) and you second trial (going up 1 by 1 until it breaks)

Perhaps you can consider:

"Going up multiple steps can reduce the number of preliminary tests to identify a range of values of X (number of steps) by a factor of number of steps you skip.

However, going up too many steps at one go before dropping the bottle reduces the precision of the preliminary test, limited to (1 - n) number of steps.

As such, there is a need to identify the most efficient n number of steps to take in the preliminary test to reduce the number of trials needed, but also provide sufficient precision such that the number of trials in the second test is minimised to ensure a most efficient method."

 

[Charles Link]

Hopefully the Mentors don't decide this is a homework problem, and belongs in the homework section using the Homework template. Suggestion is to start with rung 50, then go to 75, and then to 87, and 94, etc. if the bottle survives. Once it breaks, you are stuck with going rung by rung with the 2nd bottle, in single steps, starting one rung above where your first bottle survived, until it breaks. $\\$ Editing: Then of course, there are alternate ways, going 1/3 of the way up as a starting point, with less chance of breaking the first bottle in this manner. An interesting problem, and it could get even more interesting if you had 3 bottles to work with, etc.

 

[srfriggen]

In my original method I think we can break the problem down to a simpler one with just 10 rungs and get the same answer, since the worst case is always looking at between 90 and 100. Something to do with the fact that we count in base 10?

 

[Charles Link]

In my original method I think we can break the problem down to a simpler one with just 10 rungs and get the same answer, since the worst case is always looking at between 90 and 100. Something to do with the fact that we count in base 10?

Interesting. Starting at rung 10, and then going to 20, and 30, is certainly one solution that could be quite optimal. It would be a difficult statistics problem to compute the mean number of trials needed for a given prescription or algorithm, starting with a randomly chosen rung between 1 and 100. Qualitatively, your solution looks very good.

 

[Mark44]

Hopefully the Mentors don't decide this is a homework problem

The thread is OK here, IMO.

 

[Charles Link]

In my original method I think we can break the problem down to a simpler one with just 10 rungs and get the same answer, since the worst case is always looking at between 90 and 100. Something to do with the fact that we count in base 10?

It would seem to be that the optimal solution is an interval of 10 because it is the square root of 100. Had it been 400 rungs, an interval of 20 might have been optimal.

 

[mfb]

If you have to go up a fixed number of rungs (x) with the first bottle the worst case for a ladder with n rungs is approximately n/x + x, this is minimal for $x=\sqrt n$. This is not the best possible strategy, however. Start with larger initial steps, reduce the step size later. If you want to minimize the worst case, make sure the worst case for every outcome of the first bottle is the same. If you want to reduce the expectation value, the problem gets more interesting.

 

[StoneTemplePython]

To be clear we're not talking about minimizing an expected number of iterations -- were just talking about minimizing the maximum number of iterations (without breaking both bottles), right?

It would seem to be that the optimal solution is an interval of 10 because it is the square root of 100. Had it been 400 rungs, an interval of 20 might have been optimal.

This sounds about right... it certainly feels like $GM\leq AM$ -- i.e. the problem asks us to minimize the arithmetic mean given a geometric mean...

 

[CWatters]

If you can write an equation for the number of trials vs interval then perhaps look up how to find the minimum or maximum of a curve. It involves differentiation.

 

[willem2]

You'll get a lot more hits if you search for "two egg drop problem"
There seem two be two ways to write a recurrence. One of them is to use the number of tries as a function of the number of eggs (e) and the number of possible floors where the egg could still break (n). This seems to be what most websites do.
You'll get something like this. $$f(n,e) = 1+ \min_{0<i<n} \max (f(i,e-1), f(n-i,e))$$
It's still easy enough for a computer for even a 1000 floors, if you store all f(n,e) in an array. It's not so easy to get an explicit formula.

However it's much better to work with the maximum number of floors you could search, as a function of the number of eggs and the number of tries.
You then get f(t,e) = f(t-1, e-1) + 1 + f(t-1,e), and the min/max stuff is gone.
if you have t tries and e eggs, you should break the egg at floor f(t-1, e-1) +1
An explicit formula for f(t,2) should now be easy to find., since f(t,1) = t.
​

 

[srfriggen]

So apparently the solution is much easier (for me to understand, anyway). You go up 14, then up 13, then 12, then 11, etc. This fixes the max number of drops at 14.

n+(n-1)+(n-2) + ... > n

You can write this sum of an arithmetic sequence and then solve as a quadratic.

 

[mfb]

That is the solution to my suggestion in post 8:

If you want to minimize the worst case, make sure the worst case for every outcome of the first bottle is the same.

If you reduce the number of steps by 1 each time, the worst case is always the same - one more step by the first bottle means one step less with the second one.

 

[srfriggen]

I'm sorry I didn't understand it the first time.

 

[epenguin]

I would have thought that the optimum strategy would have been to go to rung 50 on the first trial, and continue like that always going halfway into the 'unknown' zone. Each trial halves the span where the critical rung might be, and at worst you identify it after 7 or 8 trials. With any strategy you might get lucky and identify in 2 trials, but much more often you would be unlucky.

 

[jbriggs444]

I would have thought that the optimum strategy would have been to go to rung 50 on the first trial, and continue like that always going halfway into the 'unknown' zone. Each trial halves the span where the critical rung might be, and at worst you identify it after 7 or 8 trials. With any strategy you might get lucky and identify in 2 trials, but much more often you would be unlucky.

If you had an infinite number of bottles to break (or at least 7), that could work. But with only two bottles you might end up with:

Drop from 50: Break
Drop from 25: Break
Error: no more bottles.

 

[epenguin]

Ah well if you're going to start telling me to read the question…

I was reading the first answer which seemed to assume you had loads of bottles. Well seven is enough.Seems the fastest wayOn average in that case.

But if I only had to have my two and I don't mind if they are both broken as long as I get to know the rung, the sure way seems be to go up to the second rung, and then every second rung until the bottle breaks, then you go down one rung and you will identify exactly the critical rung.

Hmm, but you could go halfway up the first time, and after that you would have to go one at a time either from the first step or the halfway up step. Looks like every time you gain information by doing several steps, it is offset by the number of steps you then have to do, so it looks like might be a finicky calculation about small differences.

 

[jbriggs444]

Ah well if you're going to start telling me to read the question…

Might not hurt to read the thread too. The better approaches do the required finicky calculations systematically.

 

[Stephen Tashi]

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.

I think of it as wanting to find the highest rung at which bottles can be dropped without breaking, but maybe you start counting rungs from the top.

Although the puzzle could approached as a problem in probability modeling, I don't think the poser of the problem intends to ask about minimizing the expected number of trials that will be needed. Thinking conventionally, this a game theory type of puzzle, a "mini-max problem". The goal is to find the strategy that minimizes the number of trials if our adversary (Nature) can pick a strategy that tries to maximize them at every trial.

We looked at worst case scenarios.

That is the correct approach to a game theory type problem.

So when you write-up you answer to the puzzle, you should include your interpretation of what the puzzle is asking.

 

[deRoy]

Ok, let's see..

1) I would start with rung 1 first, for if the first bottle breaks it's just 1 trial. If not then I would move to rung 51.

2) If the first bottle doesn't break, I would move to rung 52 for if it breaks as in case 1) it's just two trials so far. If not then move 100-52 = 48/2 = 24 plus 1 steps up = rung 77.

3) If the first bottle still doesn't break move to rung 78. If it breaks it's just 3 trials. If not move to 100-78 = 22/2 = 11+1 steps up to rung 91.

4) If the first bottle still doesn't break move to rung 92. If it breaks it's just 4 trials. If not move to 100-92 = 8/2 =4 +1 steps up to rung 97.

5) If the first bottle still doesn't break move to rung 98. If it breaks it's just 5 trials.

In the extreme case that the first bottle breaks when dropped from the 100th rung you have found it with only 7 trials.

Well, someone said before, to proceed by 10 rungs. But if the first bottle breaks on the 10th rung, you have to go up 90 rungs with the second bottle on the ladder if it were to break from rung 100 say. The right way to proceed is to go up the ladder in half the number of the remaining rungs each time.
Now, checking two ladder rungs at a time before moving further up seems overkill to me, but I would try it even if it's not mathematically correct to diminish the probabilities.

 

[mfb]

@deRoy: If the bottle breaks on step 50, what do you do? You have to test step 2, step 3, step 4, .. all with the single remaining bottle. In the worst case you need 50 tests.
Testing step 1 first is extremely wasteful, and testing step 50 as second case makes the situation really bad if it breaks there.

Well, someone said before, to proceed by 10 rungs. But if the first bottle breaks on the 10th rung, you have to go up 90 rungs with the second bottle on the ladder if it were to break from rung 100 say.

No. You know it breaks at 10, you only have to test numbers smaller than that with the second bottle.

The right way to proceed is to go up the ladder in half the number of the remaining rungs each time.

That gives you a really bad worst case and a very poor average case as well.

 

[mfig]

I would think a strategy where we go up a fixed percentage of the remaining number of rungs above our previous guess would give a lower expected number of guesses than taking uniform jumps. For example, if we pick a ratio of 1/10, then guesses would be 10, 19, 28 etc. If we pick a ratio of 1/5, then the guesses would be 20, 36, 49, etc. I take it that once the first bottle is broken, the breaking rung is discovered by going up one rung at a time to ensure the correct rung is found.

Perhaps not, but this strategy seems more intuitive. This could be easily checked with a computer.

 

[jbriggs444]

I would think a strategy where we go up a fixed percentage of the remaining number of rungs above our previous guess would give a lower expected number of guesses than taking uniform jumps.

An attractive approach, but not optimal.

I take it that once the first bottle is broken, the breaking rung is discovered by going up one rung at a time to ensure the correct rung is found.

Yes, that is the only viable approach for the second bottle.

 

[mfig]

An attractive approach, but not optimal.

Does this mean you think uniform jumps would yield a lower expected number of trials, or do you think some other approach entirely is optimal?

 

[jbriggs444]

Does this mean you think uniform jumps would yield a lower expected number of trials, or do you think some other approach entirely is optimal?

A slightly different approach is optimal. And is given earlier in this thread.

 

[mfb]

A slightly different approach is optimal. And is given earlier in this thread.

What we had earlier in the thread is the optimal worst case.

For the optimal expectation value, small changes improve it a bit. I have no proof that it is perfect, but here is the best I found:
13, 26, 38, 49, 59, 68, 76, 83, 89, 94, 97, 99, 100 - with an expected 10.32 attempts (where the solution posted before has an expectation value of 10.34).

 

[Tom.G]

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.

Spoiler

Looks more like a reading comprehension test!

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

As written, the answer is obviously either One or None.
EDIT in Blue.

p.s. The edit occurred to me as I was falling asleep last night, however by then sleep had gained a higher priority.

Cheers,
Tom