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?

  • $\begingroup$ "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"? $\endgroup$ – John L. Oct 29 '18 at 23:31
  • 1
    $\begingroup$ 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 $\endgroup$ – John L. Oct 29 '18 at 23:37
  • $\begingroup$ 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? $\endgroup$ – Yuval Filmus Oct 30 '18 at 4:44
  • $\begingroup$ 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? $\endgroup$ – Yuval Filmus Oct 30 '18 at 5:21

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.


Your Answer

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

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