Istvan Kovacs

Ranch Hand

Posts: 100

posted 7 years ago

Suppose you have two identical, solid objects. They will break if dropped from a great height, but you don't know exactly how far you have to lift them. There's a 50-storey building you can be sure is tall enough, so if you drop them from the 50th floor, they will break.

You want to learn which is the lowest numbered floor that is high enough for the objects to break if dropped from that floor.

What is the minimal number of experiments needed to find that floor (in the worst case)? You have 2 objects, each of them can only be used until it breaks :-)

You want to learn which is the lowest numbered floor that is high enough for the objects to break if dropped from that floor.

What is the minimal number of experiments needed to find that floor (in the worst case)? You have 2 objects, each of them can only be used until it breaks :-)

Rohan kanade

Ranch Hand

Posts: 106

Istvan Kovacs

Ranch Hand

Posts: 100

Istvan Kovacs

Ranch Hand

Posts: 100

Mike Simmons

Ranch Hand

Posts: 3090

14

Ryan McGuire

Ranch Hand

Posts: 1136

8

posted 7 years ago

I agree with an answer of 10.

I came up with the start of the pattern that you probably figured out, Mike. I started with a guess of 15 tests and figured out the pattern for that. "If I have to make a decision in 15 test, I can start at floor Q. If my first thingy breaks, I test floors R-S. If it doesn't break, I go up to floor T, etc." Once I saw the pattern of floors (Q, T, etc.) for 15, the correct answer of 10 was easy to determine.

Of course, there might be a strategy that I didn't see that yields a smaller minimum. ...but I doubt it.

Follow-up question: What if you had 3 identical breakable objects and an 80-story building? How about N breakables and an M-story building? Even if you can't write the complete formula, how would you go about solving it?

Mike Simmons wrote:Seems a little early to give up, isn't it?

I have a solution requiring 10 drops. I believe this is optimal for the problem as stated. But I'll give others a chance before I reveal more details.

I agree with an answer of 10.

I came up with the start of the pattern that you probably figured out, Mike. I started with a guess of 15 tests and figured out the pattern for that. "If I have to make a decision in 15 test, I can start at floor Q. If my first thingy breaks, I test floors R-S. If it doesn't break, I go up to floor T, etc." Once I saw the pattern of floors (Q, T, etc.) for 15, the correct answer of 10 was easy to determine.

Of course, there might be a strategy that I didn't see that yields a smaller minimum. ...but I doubt it.

Follow-up question: What if you had 3 identical breakable objects and an 80-story building? How about N breakables and an M-story building? Even if you can't write the complete formula, how would you go about solving it?

Mike Simmons

Ranch Hand

Posts: 3090

14

posted 7 years ago

Hey - someone snuck a new question in after I read their last post. No fair!

Fortunately, it was essentially the same question I was thinking about...

8 drops. Or if you had 4 identical breakable objects, then 7 drops. Unfortunately, after this you no longer can reduce the number of drops by increasing the number of objects. You need 7 drops for any number of objects greater than 3, to solve an 80-story building.

Well, I don't have a single analytic formula for that (yet), but I do have a fairly simple algorithm for making a table to solve it. I have a feeling further simplification is possible though, so I'll post more later.

Fortunately, it was essentially the same question I was thinking about...

Ryan McGuire wrote:Follow-up question: What if you had 3 identical breakable objects and an 80-story building?

8 drops. Or if you had 4 identical breakable objects, then 7 drops. Unfortunately, after this you no longer can reduce the number of drops by increasing the number of objects. You need 7 drops for any number of objects greater than 3, to solve an 80-story building.

Ryan McGuire wrote:How about N breakables and an M-story building? Even if you can't write the complete formula, how would you go about solving it?

Well, I don't have a single analytic formula for that (yet), but I do have a fairly simple algorithm for making a table to solve it. I have a feeling further simplification is possible though, so I'll post more later.

Ryan McGuire

Ranch Hand

Posts: 1136

8

posted 7 years ago

If not a closed form formula, how about a recursive formula?

Since the original problem, is to find T given B and S(), you could say the answer is...

Granted, plugging various values of T into the recursive formula for S() to find the smallest T is more of an algorithm than a formula. Nonetheless, it does give you a way to find the answer regardless of inputs. It might take a while, but it will conclude.

Or....

You could pre-calculate a table of values for S() for various values of T and B:

- Fill in row T=0 with 0

- Fill in column B=1 with T

- For all the other tables cells, fill in a value that is the sum the cell value immediately above (S(B, T-1)), the cell value above and to the left (S(B-1,T-1)) and 1.

That sounds a lot like Pascal's Triangle, doesn't it? I'll leave the derivation of the closed form as an exercise for the interested reader.

In the breakable items B=2 column, a 50-story building falls between the rows for T=9 and T=10. Nine tests isn't enough, ten tests is.

What about the other case I posed: S() = 80, B=3? In column B=3, S()=80 between rows T=7 and T=8. The answer, as Mike calculated, is 8. Beautiful.

Mike Simmons wrote:Hey - someone snuck a new question in after I read their last post. No fair!

Fortunately, it was essentially the same question I was thinking about...

Ryan McGuire wrote:Follow-up question: What if you had 3 identical breakable objects and an 80-story building?

8 drops. Or if you had 4 identical breakable objects, then 7 drops. Unfortunately, after this you no longer can reduce the number of drops by increasing the number of objects. You need 7 drops for any number of objects greater than 3, to solve an 80-story building.

Ryan McGuire wrote:How about N breakables and an M-story building? Even if you can't write the complete formula, how would you go about solving it?

Well, I don't have a single analytic formula for that (yet), but I do have a fairly simple algorithm for making a table to solve it. I have a feeling further simplification is possible though, so I'll post more later.

If not a closed form formula, how about a recursive formula?

Since the original problem, is to find T given B and S(), you could say the answer is...

Granted, plugging various values of T into the recursive formula for S() to find the smallest T is more of an algorithm than a formula. Nonetheless, it does give you a way to find the answer regardless of inputs. It might take a while, but it will conclude.

Or....

You could pre-calculate a table of values for S() for various values of T and B:

- Fill in row T=0 with 0

- Fill in column B=1 with T

- For all the other tables cells, fill in a value that is the sum the cell value immediately above (S(B, T-1)), the cell value above and to the left (S(B-1,T-1)) and 1.

That sounds a lot like Pascal's Triangle, doesn't it? I'll leave the derivation of the closed form as an exercise for the interested reader.

In the breakable items B=2 column, a 50-story building falls between the rows for T=9 and T=10. Nine tests isn't enough, ten tests is.

What about the other case I posed: S() = 80, B=3? In column B=3, S()=80 between rows T=7 and T=8. The answer, as Mike calculated, is 8. Beautiful.

Mike Simmons

Ranch Hand

Posts: 3090

14

posted 7 years ago

Yep - generating that table was what I meant by having a fairly simple algorithm to make a table to solve it. And I saw how it is tantalizingly similar to Pascal's triangle, but diverges. Which is why I thought there may well be more to it, and perhaps a simpler form. But I haven't done anything else with the problem since that post.

Ryan McGuire

Ranch Hand

Posts: 1136

8

posted 6 years ago

Just in case anyone uses this problem / solution later...

There are some incorrect values in the table I generated. The repeating value near the end of row T=6 should be 63. All the values that derive from those values will be incorrect as well. At least the formula is correct.

I'll leave it as an exercise for the interested reader to fill in the correct values. Knowing that you have a problem is the first step to recovery.

Ryan McGuire wrote:

Just in case anyone uses this problem / solution later...

There are some incorrect values in the table I generated. The repeating value near the end of row T=6 should be 63. All the values that derive from those values will be incorrect as well. At least the formula is correct.

I'll leave it as an exercise for the interested reader to fill in the correct values. Knowing that you have a problem is the first step to recovery.

It is sorta covered in the JavaRanch Style Guide. |