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.