# Balancing subproblems in resilience testing

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?

## migrated from cstheory.stackexchange.comMay 13 '13 at 2:27

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

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

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.