# Egg dropping puzzle

My problem is a modification of the known problem. Suppose you have a building with n floors. (Where n can be any size). Furthermore you have an indestructible egg at your disposal. If the egg is thrown from a floor which is not the maximum one gets a message. If the floor was too high you don't get a message. How can I design an algorithm that uses minimum many tests without knowing the height of the building? What is the minimum asymptotic runtime of such an algorithm?

• "If the egg is thrown from a floor which is not the maximum one gets a message." Do you mean if the egg is not thrown from the $n^{th}$ floor, one gets a message? If you mean some floor is designated as the maximum floor, will there be a message or not if the egg is thrown on a floor lower than that maximum floor? Which floors are considered "too high"? – John L. Oct 29 '18 at 23:31
• The known problem must be referring to something like the problem of finding maximum number of floors you can check with N eggs and D maximum drops – John L. Oct 29 '18 at 23:37
• I'm not sure your question is well-defined. What do you mean by minimum number of tests? For any given algorithm, the number of tests depends on the answer. Can you be more formal? – Yuval Filmus Oct 30 '18 at 4:44
• I can think of at least two reasonable models. Assuming that the number of floors is $n$ and that you throw the egg from floor $m$, you get to find out whether (1) $n=m$ or whether (2) $n<m$ (or $n \leq m$, which is the same). Which one is it? – Yuval Filmus Oct 30 '18 at 5:21

## 1 Answer

Suppose that the true number of floors is $$n$$. Your question is unclear, but it seems that you are interested in the minimum number of queries of the form "$$n < m$$?" needed to find $$n$$.

Let us start with a lower bound. Consider a strategy for the task that works for every $$n$$. We can associate with each $$n$$ the transcript of the strategy, which is the list of yes/no answers to the queries performed by the strategy. These transcripts constitute a prefix code (why?), and so the number of queries $$a_n$$ asked when the answer is $$n$$ satisfies Kraft's inequality: $$\sum_{n=1}^\infty 2^{-a_n} \leq 1.$$ In particular, $$\limsup (a_n - \log n) = \infty$$ (since the series $$1/n$$ diversges), which we write as $$a_n \gg \log n$$; here $$\log n = \log_2 n$$. Similarly, $$a_n \gg \log n + \log \log n$$ (since the series $$1/n\log n$$ diverges).

Let us now attempt to design strategies. One simple strategy asks whether $$n < 2^t$$ for $$t=1,2,\ldots$$, until finding a value of $$t$$ such that $$2^t \leq n < 2^{t+1}$$; this takes $$\log n + O(1)$$ queries. Binary search over $$2^{t+1}$$ takes $$\log n + O(1)$$ more queries, for a total of $$2\log n + O(1)$$.

A better strategy applies the above strategy recursively on the $$t$$'s. The first step is to ask whether $$n < 2^{2^s}$$ for $$s=0,1,\ldots$$, until finding a value of $$s$$ such that $$2^{2^s} \leq n < 2^{2^{s+1}}$$; this takes $$\log \log n + O(1)$$ queries. Binary search over $$2^{2^s},2^{2^s+1},\ldots,2^{2^{s+1}}$$ finds a value of $$t$$ such that $$2^t \leq n < 2^{t+1}$$ in $$\log \log n + O(1)$$ more steps, and finding $$n$$ using another binary search takes $$\log n + O(1)$$ steps, for a total of $$\log n + 2\log\log n + O(1)$$ steps.

The two strategies are completely analogous to Elias' gamma coding and delta coding. It is likely that Elias' omega coding can likewise be implemented.