Magical eggs and tiny floors

Question

You are given 4 eggs and a 30 floor building.  You need to figure out the highest floor an egg can be dropped without breaking, assuming that (i) all eggs are identical, (ii) if an egg breaks after being dropped from one floor, then the egg will also break if dropped from all higher floors, and (iii) if an egg does not break after being thrown from a certain floor, it retains all of its strength and you can continue to use that egg. Your goal is to minimize the number of throws. From which floor do you drop the first egg? How do you handle this problem given generally m eggs and an n-floor building?

Answer 1

We can use dynamic programming to solve this problem.

Notation: M[i][j]: The minimized number of throws when we have i eggs and j floors to test. We also have the base case: M[n][1]=1, M[1][n]=n.( Note: If we just have 1 floor, we only have to throw one time; If we have 1 egg and n floor to try, we can start at the first floor and we may have n throws in the worst case.)

Optimality: We can throw the egg from k floor at first. If the egg is broken, we will test the remaining (j-k) floors in the worst case; if the egg is not broken, we will test the remaining (k-1) floors in the worst case.

Recurrence relation: M[i][j] = min{max{M[i-1][k-1],M[i][j-k]} + 1}  ( Note: We use the max at here because we need to consider the worst case of them. )

Algorithm: 

for i = 1 to m
         for j = 1 to n
                for k = 1 to n
                    M[i][j] = min{max{M[i-1][k-1],M[i][j-k]} + 1} 

Answer 2

I agree with the Roc6212, this is generally a searching problem, binary search tree seems most efficient. As shown below, a 30 floor building requires a 5 levels tree, which suggests a maximum of 5 tests needed.            

                                              16

                 8
  
       4                     12                                   .................

  2       6          10         14

1   3   5   7    9    11   13     15

Suppose the highest floor = X. Current testing floor = T

As every failed test(X<T) that consumes the egg will result in traversing the left tree, In the case that X<=1, the four left traversals will break all four eggs and left 1 untested.(I assume the egg can also be broken at level 1 then we still need to test it). Although in other cases when X>1, there will be at least one right traversal so 4 eggs is enough. 

Hence, an improved way to build the tree is eliminate the leftmost element, so that the last traversal cannot be left.

                                              15

                 7
  
       3                     11                                   .................

  1       5          9          13

    2   4   6    8    10   12     14

In this scenario we can choose 15 at the beginning, on the left tree we have 14 floors, on the right side we have 15 floors. And the maximum floors that we can test for 4 eggs is exactly 30 floors.

So generally the maximum number of floors that can be test in one round(one tree) is 2^m+1-2， for n>2^m+1​-2, we can divided into several rounds: 1 to 2^m+1​-2, 2^m+1​-1 to 2^m+2-4,  ...... Notice if X> 2^m+1-2, the first round test will preserve all the eggs. Hence we can test each round sequentially and each round will have full m eggs to test.

/***********Update******************/

In fact, for situation that n>2^m+1​-2,  we can use an unbalance binary tree(right heavy) as long as it satisfies the condition that for all the possible paths, the left traversals do not exceed m. I think this method can always beat the previous one(sequential round). And the analysis of average steps is a more complicated. 

For general case, we will need to first calculate the total depth of the tree. Let n_m(d) denotes the items contained in our tree, m = eggs, d = depth, the tree rooted at depth 1.

Once we get the depth, we can calculate the size of left tree and get which testing floor we should choose. And the current test floor should be 1+n_m-1(d-1) .

Comments

For example, say there are 100 floors and only 2 eggs.  What would be the answer then?

---

The selected floor will go as 14,27,39,50,60,69,77,84,90,95,99(or 98). This order assumes that X always larger then selected floor. Whenever X smaller than selected floor, then one egg is broken, the test should then starts from the  lowest to the highest between the range.

For example, after the first throw, if X>14, the second throw should be 27, if X<27, then the test should be carried out for each floor ranged from 15 to 26 in ascending order.

In this case, the depth of the tree is 14. So the maximum throws required will not exceed 14. This number is calculated through discovering the left tree has d elements and right tree has (1+d)*d/2 elements, where d is the depth.

Am I in the right direction?

---

Mingyu, yes, you seem to be in right direction.   Now, to answer the original question - what is the answer for general n floors and m eggs.

---

I have updated the answer, sorry about the delay, it's been a long orientation week.

Answer 3

we have m floors and n eggs.

If we have n₁ eggs and we have a try on the m₁ th floor, then it could come into one of the two results.

That is, 

If the egg is broken, the scale is shorten to [0,(m₁-1)] ,also, the number of egg now will be n₁-1.

if the egg is not broken, the scale is shorten to [m₁,m],which equalvalant to the[0,m-m₁],and the number of egg will still be n_1.

Consider the condition we only have 1 egg, which is the subset of that question, the only way is to try it step by step, and finally, we will try m(the amount of floors) times to solve the problem.

Another condition is that we consider there is enough eggs(enough to do the binary search),we will try floor(log₂ m)+1 times.

 

Comments

Please wait for some time for my code, I am debugging...

---

I like the answer.  Perhaps this can be put into a recursive way?

Answer 4

You should start from 15th or 16th floor, which is the middle of all floors. If the breaks, you exclude all the higher floors, otherwise you exclude the lower floors. Then you throw from the middle of the remaining floors. Repeat this process for 4 times and you get the answer.

Given m eggs and n floors, you can start from the middle of n floors, which is n/2 + 1 or (n+1)/2, and you follow the above process and you can repeat m times or more (if the eggs do not break all the times). After the last time you throw the egg, you do one more time exclusion according to whether the egg breaks, then you have your answer as the middle of remaining floors. You might not get the exact highest floor, but this is the way to get close.

Comments

What is the general approach?

---

Dear Prof Arora, the second paragraph is the general approach.

Answer 5

First I try to solve this question by mathematics.I think we could divide the floors in same region.If the first is broken, I could make sure the broken region is below this floor.The number of layers is n , f is the times in worst case, making expression:f=100/n+(n-1)-1.Using average inequality to find n=10,hence f=18.

Nevertheless,this solution still has problem.For instance,on the 19th and 79th,the time of worst case is 10 and 16:

9th f=9

19th f=10

29th f=11

.....

99th f=18

Hence I adjust my solution,distribute the floor as an minus 1arithmetic sequence to balance worst case times.

Since the expression is n+(n-1)+(n-2)+······+2+1>=100

n =14 (but I do not know how to summary in general.)

Hence I agree with the Yihe Wang,this is a dynamic programming problem.Suppose there is m floor, n eggs, in the i layer this question will appear two kinds of state, one state is the eggs break, than we have only (n-1) eggs while the total number of floor also reduced to (i-1), another is the egg did not break, so the total number of eggs is unchanged, (n) , the number of floors is reduced to the (m-i) layer.

Since we need the minimum of the worst case,there is the equation :

F(n,m)=min{max{F(n-1,i-1),F(n,m-i)}+1|1<=i<=m}

Hence I use Java to solve this question

//code

public class Solution{
    public int getFloor(int e,int f){
        if(e == 0)
        {
            return 0;
        }else if(f <= 1)
        {
            return e;
        }
        int[][] Min = new int[e+1][f+1];
        for(int i=1;i<=e; i++)
        {
            for(int j=1; j<=f; j++)
                Min[i][j] = j;
        }

        for(int n=2; n<=e; n++)
        {
            for(int m=2; m<=f; m++)
            {
                for(int k=1; k<m; k++)
                {
                    Min[n][m] = Math.min(Min[n][m],1+Math.max(Min[n-1][k-1],Min[n][m-k]));
                }
            }
        }
        return Min[e][f];
        
    }
    public static void main(String[] args)
    {
        Solution eggs = new Solution();
        System.out.println(eggs.getFloor(4,30));
    }
}

//code

The answer is 5.