You have a set of k identical glass jars and a ladder with n rungs. You want to

Question

You have a set of k identical glass jars and a ladder with
n rungs. You want to determine the highest rung of the ladder from which a jar can be dropped and not break. If
k = 1 the only way to accomplish the goal is to test rung 1, 2, 3 ...until the jar breaks. If k is sufficiently large
(roughly lgn) you could perform binary search on the rungs of the ladder (keep track of the smallest and largest
possible rungs that could be the solution and test the rung halfway inbetween).
If k = 2 what is the minimum number of drops necessary to achieve your goal (as a function of n)?
For general k what is the minimum number of drops necessary to achieve your goal (as a function of n)?

Explanation / Answer

With only one jar (k=1), we can't risk breaking the jar without getting an answer. So we start from the lowest rung on the ladder, and move up. When the jar breaks, the previous rung is the answer; if we are unlucky, we have to do all n rungs, thus n trials.
Now lets think of k=log(n): with log(n) or more jars, we have enough jars to do binary search, even if jars are broken at every rung. So in this case we need log(n) trials. Note that we can't do binary search with less than log(n) jars, as we risk breaking all jars before arriving at an answer in the
worst case.}

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.