0
$\begingroup$

Highest Safe rung problem : There are many rungs on a ladder in increasing order of height. A bottle is thrown from a rung, and depending on the height of the rung, the bottle may break or may not (bottle breaks for higher height rungs, and doesn't for lower rungs). We need to find the maximum height safe rung for which the bottle doesn't break given that:

(1) We have only 1 bottle with us.

(2) We have infinite bottles with us.

(3) We have exactly 2 bottles with us.

(4) We have k bottles with us. ($1 \leq k$).

Design algorithms for solving (1) - (4) in best possible time complexity. (Also note that (3) and (4) should be an asymptotic improvement over (1).]

My method: (1) is just a linear search and (2) is a divide and conquer approach to solving the problem. I cannot find an asymptotically improved algorithm for (3) - the only methods which I kept thinking of provide some constant factor improvements in time complexity over (1), I am absolutely clueless on how to solve for (3) and (4).

P.S: This is a problem from Chapter 1 of Kleinberg and Tardos. I couldn't find it's solution online.

$\endgroup$
  • 1
    $\begingroup$ For (3): throw the first bottle in increments of $\Theta(\sqrt{n})$ rungs, where $n$ is the total number of rungs. When the bottle breaks use strategy (1) on the interval of $\Theta(\sqrt{n})$ rungs between the last 2 throws. For a generic number $k>1$ of bottles: throw the bottle in increments of $\Theta(n^{\frac{k-1}{k}})$ rungs until it breaks. Then use the strategy for $k-1$ bottles on the the interval of $\Theta(n^{\frac{k-1}{k}})$ rungs between the last two throws. Write down the resulting recurrence equation to get an upper bound of $O(n^\frac{1}{k})$ throws for any constant $k\ge 1$. $\endgroup$ – Steven Oct 17 at 19:22
  • 1
    $\begingroup$ Your problem is known as the egg dropping puzzle (or similar names). Your question has been answered repeatedly on this site, as well as in many other online sources. $\endgroup$ – Yuval Filmus Oct 17 at 20:31
  • 1
    $\begingroup$ geeksforgeeks.org/egg-dropping-puzzle-dp-11 $\endgroup$ – asds_asds Oct 17 at 20:51
  • $\begingroup$ To find optimal answer you should use dynamic programming. For very large $k$ the answer is $O(\log n)$. $\endgroup$ – Marcelo Fornet Oct 18 at 5:48

Your Answer

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

Browse other questions tagged or ask your own question.