This week's giveaway is in the Android forum. We're giving away four copies of Android Security Essentials Live Lessons and have Godfrey Nolan on-line! See this thread for details.

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 :-)

Rohan kanade wrote:use binary search.
maybe it will take 2-3 iterations.

You cannot use binary search.
Suppose you start at the middle, floor #25. You drop one of the objects. It breaks.
Now you go to floor 12 or 13. You drop the other object. It breaks.
What now?

Rohan kanade
Ranch Hand

Joined: Oct 22, 2009
Posts: 106

posted

0

so what is the solution?

Istvan Kovacs
Ranch Hand

Joined: May 06, 2010
Posts: 100

posted

0

Rohan kanade wrote:so what is the solution?

Don't want to spoil the fun for the others. I'll sent it in PM.

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

Joined: Mar 05, 2008
Posts: 3003

9

posted

0

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.

Ryan McGuire
Ranch Hand

Joined: Feb 18, 2005
Posts: 1006

3

posted

0

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

Joined: Mar 05, 2008
Posts: 3003

9

posted

0

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

Joined: Feb 18, 2005
Posts: 1006

3

posted

0

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.