Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

You have two identical eggs. Standing in front of a 100 floor building, you wonder what is the maximum number of floors from which the egg can be dropped without breaking it. What is the minimum number of tries needed to find out the solution?

share|improve this question
1  
@Dennis: You can have more than two tries: an egg doesn’t necessarily break when you drop it. –  Brian M. Scott Oct 22 '12 at 12:28
3  
@Dennis: Of course, we probably are to assume that a successful drop doesn’t weaken the egg, which seems rather unlikely! –  Brian M. Scott Oct 22 '12 at 12:30
1  
@GiovanniDeGaetano: You've proven that the minimum number of tries is $\leq 20$. In fact, if you go through your argument carefully, I think you actually get an upper bound of $19$. [Worst case: try floors $10, 20, \dots, 90, 91, 92, \dots, 99, 100$. I think you have to try floor $100$ in case it lands unbroken from floor $99$ since you aren't told that you know it will definitely break if dropped from floor $100$.] But you might be able to get a bit better by testing $\sqrt{M}$ floors above your previous one, where $M$ is the number of remaining steps. –  Michael Joyce Oct 22 '12 at 13:06
1  
1. The egg breaks, and you have one egg to test for the remaining $k-1$ floors. By the first paragraph, this implies you will need $k$ moves in total. 2. The egg doesn't break; in this case, the first $k$ floors don't matter, and you are playing with 2 eggs and $100-k$ floors, and thus you need $1+f(100-k)$ moves in this case. So this should let you code a solution to the problem. –  only Oct 22 '12 at 13:16
3  
The answer is $0$: If you drop an egg onto the pavement below from a first-floor (or higher) window, then it will break. –  John Bentin Oct 22 '12 at 13:29

3 Answers 3

up vote 7 down vote accepted

Now that you have got the answer by yourself, let me post what I was going to, as well. (A slow formal proof that $14$ is the minimum, and the answer for general $N$ in place of $100$.)


Just to be clear, the assumption in the problem is that all answers are possible, from $0$ to $100$ inclusive: it is possible the egg breaks when dropped from the very first floor itself, it is possible the egg can survive a fall from even the $100$th floor, and everything in between. (Also, the result of a fall is either that the egg breaks, and can no longer be used, or that it doesn't break and the fall has no effect on it whatsoever.)

Let us first solve the problem where you have only one egg. Then it should be clear that the only solution is to drop it from the first floor, then if it doesn't break drop it from the second floor, and so on up to $100$ floors. [Proof: Suppose you first drop the egg from a height $h_1$, then if it doesn't break you drop it from a height $h_2$, and so on. Then,

  • $h_1$ must be $1$. Because if $h_1 > 1$, and it breaks when you drop it from height $h_1$, then you have the egg no more, and have no way of distinguishing between the potential answers $0, \dots, h_1-1$.
  • $h_2$ must be $h_1 + 1$, and in general $h_{n+1} = h_n + 1$, for a similar reason: if the egg breaks when you drop it from $h_{n+1} > h_{n} + 1$, then you have no way of distinguishing between the potential answers $h_{n}, \dots, h_{n+1}-1$. So $h_1, h_2, h_3, \dots$ are $1, 2, 3, \dots$ respectively. $\Box$]

So now with two eggs, suppose you drop it from a height $h_1$, then if it doesn't break you drop it from a height $h_2$, and so on. (Obviously to be optimal this will be an increasing sequence, since if the egg doesn't break when dropped from some height, it is never necessary to drop it from a smaller height as you already know the result.) For convenience, denote $h_0 = 0$. If on some drop $h_{n+1}$ the egg breaks ($n \ge 0$), then you are left with the task of distinguishing between the possible answers $h_n, \dots, h_{n+1}-1$ with just one egg, which by the reasoning of the first part above, takes (up to) $h_{n+1} - h_{n} - 1$ drops (basically you drop the egg from $h_{n} + 1$, then from $h_{n} + 2$, and so on up to $h_{n+1} -1$). So the total number of drops needed in this scenario is $n+1$ (for the drops $h_1$ to $h_{n+1}$) followed by $h_{n+1} - h_{n} - 1$ drops, for a total of $ n + 1 + h_{n+1} - h_{n} - 1$, namely $n + h_{n+1} - h_{n}$ drops (where $n\ge 0$). In the worst case, we will incur the maximum cost of this over all $n$, and that is what we want to minimize: we want to minimize $$\begin{align}\max( &0 + h_1,\\ &1 + h_2 - h_1, \\ &2 + h_3 - h_2, \\ &\dots,\\ &n + h_{n+1} - h_{n})\end{align}$$ where $n$ now is such that $h_{n+1} = 100$ (if your egg never breaks, you'll keep using the first egg until you drop it from the $100$th floor, so we can wlog assume that the $h_i$s form a finite sequence ending with $100$). Note that the sum of all these quantities telescopes, and it is $\frac{n(n+1)}{2} + 100$. So since the sum of $n+1$ numbers is that much, the largest of them is at least $\frac{1}{n+1}$th of it, namely $$\frac{1}{n+1}\left(\frac{n(n+1)}{2} + 100\right) = \frac{n}{2} + \frac{100}{n+1} \ge 10\sqrt{2} - \frac12 \approx 13.6,$$ so we need at least $14$ drops.

And the method for actually achieving $14$ drops suggests itself: to make the maximum equal when the sum is fixed, the general way is to make all of them as equal as possible, which suggests we can take $h_1 = 14$, then $h_2 - h_1 = 13$ (so $h_2 = 14 + 13 = 27$), then $h_3 = 14 + 13 + 12$, and so on up to $h_{11} = 14 + 13 + \dots + 4 = 99$, and then $h_{12} = 100$.

(There are many other solutions, e.g. $h_1 = 7$, then $h_2 = 7 + 13$, $h_3 = 7 + 13 + 12$ and so on up to $h_{14} = 7 + (13 + 12 + \dots + 2 + 1) = 100$, but the salient fact is that $13 + 12 + \dots + 2 + 1 = 91 < 100$, while $14 + 13 + \dots + 2 + 1 = 105 > 100$. If instead of $100$ we were given $105$, the answer would still be $14$, and the method would be unique.)

Of course, we did not here use any special property of $100$, and repeating the above argument for general $N$ shows that the number of steps needed is: $$ \left\lceil \sqrt{2N} - \frac{1}{2} \right\rceil$$

A simpler alternative way of saying this is: $$\text{the smallest number $n$ such that $\frac{n(n+1)}{2} \ge N$.}$$

share|improve this answer
    
A simpler argument than the above would have been to calculate what's the largest $N$ for which we can solve the problem in at most $n$ drops, and we'd have found $N$ to be $1 + 2 + \dots + n = \frac{n(n+1)}{2}$. –  ShreevatsaR Oct 23 '12 at 13:08
    
Note: On the face of it the two expressions look different (the second one algebraically gives $n = \left\lceil \sqrt{2N + \frac14} - \frac{1}{2} \right\rceil$), but because for integer $n$ we have $\frac{n(n+1)}{2}$ also an integer, we can see that $$\frac{n(n+1)}{2} \ge N \iff \frac{n(n+1)}{2} \ge N - \frac18 \iff n \ge \sqrt{2N} - \frac12,$$ so they are the same. –  ShreevatsaR Oct 23 '12 at 13:23
    
what if the egg hatches in between, did you take that possibility into account?? :):) –  dineshdileep Oct 23 '12 at 13:25
    
(btw, very nice proof!) –  dineshdileep Oct 23 '12 at 13:25

I found the solution. Here it is:

The easiest way to do this would be to start from the first floor and drop the egg. If it doesn’t break, move on to the next floor. If it does break, then we know the maximum floor the egg will survive is 0. If we continue this process, we will easily find out the maximum floors the egg will survive with just one egg. So the maximum number of tries is 100 that is when the egg survives even at the 100th floor.

Can we do better? Of course we can. Let’s start at the second floor. If the egg breaks, then we can use the second egg to go back to the first floor and try again. If it does not break, then we can go ahead and try on the 4th floor (in multiples of 2). If it ever breaks, say at floor x, then we know it survived floor x-2. That leaves us with just floor x-1 to try with the second egg. So what is the maximum number of tries possible? It occurs when the egg survives 98 or 99 floors. It will take 50 tries to reach floor 100 and one more egg to try on the 99th floor so the total is 51 tries. Wow, that is almost half of what we had last time.

Can we do even better? Yes we can. What if we try at intervals of 3? Applying the same logic as the previous case, we need a max of 35 tries to find out the information (33 tries to reach 99th floor and 2 more on 97th and 98th floor).

Interval – Maximum tries

    1  – 100
    2  – 51
    3  – 35
    4  – 29
    5  – 25
    6  – 21
    7  – 20
    8  – 19
    9  – 19
    10 – 19
    11 – 19
    12 – 19
    13 – 19
    14 – 20
    15 – 20
    16 – 21

So picking any one of the intervals with 19 maximum tries would be fine.

Instead of taking equal intervals, we can increase the number of floors by one less than the previous increment. For example, let’s first try at floor 14. If it breaks, then we need 13 more tries to find the solution. If it doesn’t break, then we should try floor 27 (14 + 13). If it breaks, we need 12 more tries to find the solution. So the initial 2 tries plus the additional 12 tries would still be 14 tries in total. If it doesn’t break, we can try 39 (27 + 12) and so on. Using 14 as the initial floor, we can reach up to floor 105 (14 + 13 + 12 + … + 1) before we need more than 14 tries. Since we only need to cover 100 floors, 14 tries is sufficient to find the solution.

Therefore, 14 is the least number of tries to find out the solution.

share|improve this answer
    
I understand your argument that it can be done in 14 tries, but why exactly is that the least number? –  Jason DeVito Oct 23 '12 at 12:07
    
@JasonDeVito Using 14 as the initial floor, we can reach up to floor 105 (14 + 13 + 12 + … + 1) before we need more than 14 tries. –  Jaguar Oct 24 '12 at 3:38
    
I understand that 14 works. What I was wondering is why, say, 13 wouldn't work. Obviously 13 wouldn't work with your chosen strategy, but who's to say there isn't some crazy approach where $13$ is sufficient? –  Jason DeVito Oct 24 '12 at 12:23

The critical strip of eggs is the interval $C:=[k,k+1]$ such that, when an egg is dropped from a height $\leq k$ it survives, and when it is dropped from a height $\geq k+1$ it brakes.

The numbers $$h_r(n)\qquad(r\geq0,\ n\geq0)$$ ("allowed length for $r$ eggs and $n$ trials") are defined as follows: If we know that $C$ lies in a certain interval of length $\ell\leq h_r(n)$ we can locate $C$ with $r$ eggs in $n$ trials, but if we know only that $C$ lies in a certain interval of length $\ell>h_r(n)$ then there is no deterministic algorithm that allows to locate $C$ with $r$ eggs in $n$ trials for sure. Obviously $$h_0(n)=1\quad(n\geq0)\ ,\qquad h_r(0)=1\quad(r\geq0)\ .$$ The numbers $h_r(n)$ satisfy the recursion $$h_r(n)=h_{r-1}(n-1)+h_r(n-1)\qquad(r\geq1,\ n\geq1)\ .\qquad(*)$$ Proof. Assume $C$ lies in a certain interval $I$ of length $\ell:=h_{r-1}(n-1)+h_r(n-1)$. We may as well assume that the lower end of $I$ is at level zero. Drop the first egg at height $h_{r-1}(n-1)$. If it brakes then $C$ is contained in the interval $[0,h_{r-1}(n-1)]$ and can be located with the remaining $r-1$ eggs in $n-1$ trials. If it survives then $C$ is contained in the interval $[h_{r-1}(n-1),\ell]$ of length $h_r(n-1)$ and can be located with the $r$ eggs in $n-1$ trials. This proves $h_r(n)\geq\ell$.

Conversely, assume that we know only that $C$ lies in a certain interval of length $\ell'>\ell$ and that there is an algorithm that locates $C$ with $r$ eggs in $n$ trials. This algorithm would tell us the height $k$ at which we should drop the first egg. If $k>h_{r-1}(n-1)$ and the egg brakes or if $k\leq h_{r-1}(n-1)$ and the egg survives it would be impossible to finish the task, as the remaining interval that contains $C$ is larger than allowed for the remaining resources. It follows that $h_r(n)\leq\ell$.

From $(*)$ we obtain $$h_1(n)=n+1\ ,\quad h_2(n)={1\over2}(n^2+n+2),\quad h_3(n)={1\over6}(n^3+5n+6)\qquad(n\geq0)\ .$$ As $h_2(13)<100<h_2(14)$ we need at least $14$ trials to locate $C$ (or eliminate $C\subset[0,100]$) in the original setup.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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