8
$\begingroup$

The following brief description of the known "Google Eggs Puzzle" comes mainly from the web site Google Eggs:

Google Eggs Puzzle: Given n floors and m eggs, what is the approach to find the highest floor from which eggs can be thrown safely, while minimizing the throws (not broken eggs).

The so called "highest floor" in the above problem deserves more formal definition:

"highest:" there must be a floor f (in any sufficiently tall building) such that an egg dropped from the f th floor breaks, but one dropped from the (f-1)st floor will not. Then, f-1 here is the highest floor.

Actually, the description of "highest" is an excerpt from the book "The Algorithm Design Manual (Second Edition)" by Steven S. Skiena. Being an exercise in Chapter 8 "Dynamic Programming", there are plenty of resources in Web devoted to solving the puzzle by the means of dynamic programming, like Google Eggs and The Two Egg Problem.

However, there is a question from the above book:

Show that $E(n, m) = \Theta(n^{\frac{1}{m}})$, where $E(\cdot)$ is the minimum number of throws. (Note: I have changed the notations used in book for consistency.)

It is the question that motivates my problem:

My Problem: Is there some mathematical closed form for general "Google Eggs Puzzle" with n floors and m eggs, instead of dynamic programming recurrence, and of course tighter than the $E(n, m) = \Theta(n^{\frac{1}{m}})$ one?

Improve this question
$\endgroup$
3
  • 4
    $\begingroup$ I don't think the asymptotic bound is tight. It works when $m$ is a constant, but if you take $m = \log n$, your bound gives you a constant, which is false. I think a tight bound is $\Theta(\min_{k\leq m} kn^{1/k})$, which reproduces your bound for constant $m$, but also gives $\log n$ as the number of throws when $m$ is large enough to support the naive binary search based strategy. $\endgroup$
    – Robin Kothari
    Commented Dec 9, 2012 at 15:40
  • $\begingroup$ @RobinKothari I agree with you. The numerical experiments in the material Joy of Egg-Dropping support your observation. However, I don't catch the meaning of $\Theta(\min_{k \le m} kn^{\frac{1}{k}})$. As my guess, the parameter $k$ is the actual number of eggs in use. Then, what does it mean as a factor in $kn^{\frac{1}{k}}$ ? Thanks a lot. $\endgroup$
    – hengxin
    Commented Dec 12, 2012 at 1:23
  • $\begingroup$ I can try to explain the meaning, but it's a bit long so I'll post it as an answer. $\endgroup$
    – Robin Kothari
    Commented Dec 12, 2012 at 3:36

2 Answers 2

Reset to default
8
$\begingroup$

With m eggs and k measurements the most floors that can be checked is exactly $$n(m,k)={k \choose 0} + {k \choose 1} + \ldots + {k \choose m},$$ (maybe $\pm 1$ depending on the exact def). Proof is trivial by induction. This expression has no closed form inverse but gives good asymptotic.

Improve this answer
$\endgroup$
3
  • 4
    $\begingroup$ Just sketching the dropping strategy a little would make the answer more complete. Maybe it's not appropriate, since I guess it's not research-level. Anyway, with 2 eggs, you can skip $k$ floors on your first drop, and if it doesn't break, skip $k - 1$, and if it doesn't break skip $k - 2$, etc. Which gives $k(k+1) / 2$ as the highest floor you could reach using this strategy. $\endgroup$
    – Joe
    Commented Dec 10, 2012 at 23:58
  • $\begingroup$ @domotorp It seems constructive to examine the puzzle from the perspective you have just shown. And the equation about $n(m,k)$ can be proved by induction on $m$ and $k$. Although there is no clear closed form for the right hand side of this equation, can it give the asymptotic expression $k(n,m) = \Theta(n^{\frac{1}{m}})$? $\endgroup$
    – hengxin
    Commented Dec 11, 2012 at 13:45
  • 2
    $\begingroup$ @hengxin, yesish, because $\binom{k}{m}$ is a polynomial in $k$ of degree $m$, so this shows that holding $m$ constant gives $n(m, k) = \Theta(k^m)$. But see Robin's comment on the question. The more interesting question is whether this exact expression allows a more precise bound by approximating the binomial tail e.g. with erf. $\endgroup$
    – Peter Taylor
    Commented Dec 11, 2012 at 13:51
2
$\begingroup$

In my comment above I said perhaps $\Theta(\min_{k \le m} kn^{\frac{1}{k}})$ is a tight bound. I'm not sure about the lower bound, but since you just want an explanation for what $k$ means, I can explain the intuition using the upper bound.

As you guessed, $k$ is the number of eggs actually used. That explains the $\min$ on the outside. Now once we've decided to use $k$ eggs, here's a strategy that works: Think of the number $n$ as being written out in base $n^{1/k}$. So $n$'s representation will have $k$ "digits" (the word "digit" is usually reserved for base 10, but I'll use it here), and each digit holds a value from 0 to $n^{1/k}-1$. With our $k$ eggs, we're trying to extract the digits of $n$ one by one. First we start with the most significant digit. This can be determined by throwing an egg from the floor numbered $100..00$, $200..00$, and so on. After at most $n^{1/k}-1$ throws, we've learnt what the most significant bit is, and in the worst case we've broken only 1 egg. Now we do this for all the other digits. Since there are $k$ digits, we'll need $O(kn^{1/k})$ throws.

As a sanity check, observe that when $k=1$, this strategy boils down to dropping eggs from each floor one by one starting from floor 1. When $k = \log n$, we're just working in base 2. So this yields the binary search algorithm.

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ An interesting feature of domotorp's solution, unlike yours, is that it does not require knowing n in advance! $\endgroup$
    – Jeffε
    Commented Dec 12, 2012 at 4:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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