0
$\begingroup$

You’re doing some stress-testing on various models of glass jars to determine the height from which they can be dropped and still not break. The setup for this experiment, on a particular type of jar, is as follows. You have a ladder with $n$ rungs, and you want to find the highest rung from which you can drop a copy of the jar and not have it break. We call this the highest safe rung. It might be natural to try binary search: drop a jar from the middle rung, see if it breaks, and then recursively try from rung $n/4$ or $3n/4$ depending on the outcome. But this has the drawback that you could break a lot of jars in finding the answer.

If your primary goal were to conserve jars, on the other hand, you could try the following strategy. Start by dropping a jar from the first rung, then the second rung, and so forth, climbing one higher each time until the jar breaks. In this way, you only need a single jar—at the moment it breaks, you have the correct answer—but you may have to drop it $n$ times (rather than $\log n$ as in the binary search solution).

So here is the trade-off: it seems you can perform fewer drops if you’re willing to break more jars. To understand better how this trade- off works at a quantitative level, let’s consider how to run this experiment given a fixed “budget” of $k \ge 1$ jars. In other words, you have to determine the correct answer—the highest safe rung—and can use at most $k$ jars in doing so.

Suppose you are given a budget of $k = 2$ jars. Describe a strategy for finding the highest safe rung that requires you to drop a jar at most $f (n)$ times, for some function $f (n)$ that grows slower than linearly. (In other words, it should be the case that $\lim_{n\to\infty} f (n)/n = 0$.)

Anyone any insights how to solve this problem?

I know that the answer is $h = \sqrt n$. I know that it solves the problem. But I want to know how you got that answer, there must be a general way to do it?

$\endgroup$

migrated from cstheory.stackexchange.com May 13 '13 at 2:27

This question came from our site for theoretical computer scientists and researchers in related fields.

  • $\begingroup$ Why the answer not binary search with $k-1$ jars and linear search on the subsequence with the last jar? $\endgroup$ – Tyson Williams May 7 '13 at 22:23
  • $\begingroup$ ... because there's no such f for that strategy. $\;$ $\endgroup$ – Ricky Demer May 7 '13 at 22:41
1
$\begingroup$

Drop the first jar at the $\sqrt{n}$th rung, $2\sqrt{n}$th rung, and so on until it breaks at the $m\sqrt{n}$th rung. (This takes at most $\sqrt{n}$ steps). Then drop the second jar at every rung between the $(m-1)\sqrt{n}$th rung and the $m\sqrt{n}$th rung until you find the precise breakpoint.

$\endgroup$
-1
$\begingroup$

for k equal to 2 first drop the jar from the second rung if it breaks the safe rung is 1st rung else then drop it from 5th rung if it breaks then the safe rung lies below it and come one rung down and drop another jar if it breaks again then the safe rung is the below one else this is the safe rung you can repeat this process again and again till u find the safe rung with the help of this stratergy at the expense of k equal to 2 rungs we will find the maximum safe rung with higher efficiency

$\endgroup$
  • $\begingroup$ I don't see how this answers the question, could you explain how this forms a general strategy? Some punctuation would also help make your answer more readable. $\endgroup$ – Luke Mathieson Oct 14 '13 at 6:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.