Egg Dropping

Egg dropping refers to a class of problems in which it is important to find the correct response without exceeding a (low) number of certain failure states. In a toy example, there is a tower of $n$ floors, and an egg dropper with $m$ ideal eggs. The physical properties of the ideal egg is such that it will shatter if it is dropped from floor $n^*$ or above, and will have no damage whatsoever if it is dropped from floor $n^*-1$ or below. The problem is to find a strategy such that the egg dropper can determine the floor $n^*$ in as few egg drops as possible. This problem has many applications in the real world such as avoiding a call out to the slow HDD, or attempting to minimize cache misses, or running a large number of expensive queries on a database.

Suppose you have two eggs and you want to determine from which floors in a one hundred floor building you can drop an egg such that is doesn't break. You are to determine the minimum number of attempts you need in order to find the critical floor in the worst case while using the best strategy.

• If the egg doesn't break at a certain floor, it will not break at any floor below.
• If the eggs break at a certain floor, it will break at any floor above.
• The egg may break at the first floor.
• The egg may not break at the last floor.

One would be tempted to solve this problem using binary search, but actually this is not the best strategy, and you will see why. Try to work it out yourself and answer this question, or read on to see a detailed explanation of the problem.

Using binary search, you would have to drop the first egg from the $50^\text{th}$ floor. If it doesn't break, you would drop the same egg from the $75^\text{th}$ and so on; in the best case scenario you would be able to cover all floors with 7 drops.

But what if the egg broke in your first attempt, i.e. in the $50^\text{th}$ floor? If this happens, you are obligated to drop the remaining egg from each floor until finding $n^*$, which has the potential for $49$ drop tests, which is $O(n)$.

Remember, the problem is to determine the critical floor $n^*$, so you can't let your last egg break before finding it. Dropping your last egg from the $25^\text{th}$ floor would be quite risky because if it broke you wouldn't be able to determine the critical floor. It is clear that binary search is not the optimal solution. Knowing that, what is the best strategy? From which floor should you start? What's the minimum number of drops you would have to do in the worst case while using the best strategy?

Starting from the $14^\text{th}$ floor is the best strategy because, as we will show, the number of attempts in the worst case is always 14.

• What if the first egg breaks at floor 14?
  If the first egg breaks at the $14^\text{th}$ floor, then we should check the first floor, then the second one, until the $13^\text{th}$ floor. Doing this the total number of attempts would be 14.
• What if it doesn't break?
  Then you should check the $27^\text{th}$ floor. Why? Because if it breaks, you would have to check all the floors from the $15^\text{th}$ until the $26^\text{th}$ one (thirteen floors), which keeps the total number of attempts at 14 $\big($first attempt at the $14^\text{th}$ floor, second at the $27^\text{th}$ floor, and the twelve remaining drops from the $15^\text{th}$ floor until the $26^\text{th}$ floor$\big).$

And if it doesn't break, you would have to check the $39^\text{th}$ floor; if it breaks you would have to check all the floors from the $28^\text{th}$ until the $38^\text{th}$ one. $\big($Remember, one attempt at the $14^\text{th}$ floor, the second attempt at the $27^\text{th}$ floor, the third attempt at the $39^\text{th}$ floor, and the 11 remaining attempts at the floors $\{28,29,30,31,32,33,34,35,36,37\}$ and 38, totaling 14 attempts in this case.$\big)$

Using the same reasoning, you should check the $50^\text{th}$ floor, the $60^\text{th}$, the $69^\text{th}$, the $77^\text{th}$, the $84^\text{th}$, the $90^\text{th}$, the $95^\text{th}$, the $99^\text{th}$ and finally the $100^\text{th}$ one. See? Using this strategy you would cover all the floors and the number of attempts would never be greater than 14, even in the worst cases.

table1

Wonder how this table might look if there were 3 eggs!!...

Using other strategies, like the binary search, fewer attempts would be required in some cases (like in our first example), but it would require a high number of attempts in the worst case $($in our second example, where the egg broke in the $50^\text{th}$ floor and 50 drops were necessary in the worst case$).$

Therefore, we can conclude that using another strategy you would need more than 14 attempts in the worst case.

Now let's try to find a solution for the case where you have 2 eggs and a building with $k$ floors.

A good way to start this problem is to ask "Are we able to cover all the floors with $x$ drops?"

Suppose that in the best strategy, the number of drops in the worst case is $x$. Then, you should start at the $x^\text{th}$ floor, because if the egg breaks, you will have to check floors $1,2,3,\ldots,x-2$ and $x-1$, so the total number of drops will be $x$. If it doesn't break, you will have to check the $\big(x+(x-1)\big)^\text{th}$ floor. If the egg breaks, you will have to check the floors $x+1,x+2, \ldots, \big(x+(x-1)-1\big)$. Hence, the number of drops will be $\big(x+(x-1)-1\big)-(x+1)+1+2=x$.

Do you realize what we are doing? Based on the assumption that the number of drops will always be $x$ in the worst case, we find the floors where we should drop the egg. The crucial point here is understanding that we are not trying to find the minimum number of drops knowing the best strategy; actually, we are trying to find the best strategy supposing that the minimum number of drops is $x$, and we have to determine if covering all the floors using at most $x$ attempts is possible or not.

We can find an analytical solution to this problem:

Suppose the minimum number of attempts in the worst case, while using the best strategy, is $x$. In our attempt, we will drop the egg at the $x^\text{th}$ floor, covering $x$ floors, then we will drop it at the $\big(x+(x-1)\big)^\text{th}$ floor, covering $x-1$ floors, and the third drop would be at the $\big(x+(x-1)+(x-2)\big)^\text{th}$ floor, covering $x-2$ floors. We can see that using this strategy we would cover

$$x+(x-1)+(x-2)+(x-3) + \cdots + 2+1=\frac{x(x+1)}{2}$$

floors.

If we are able to cover $\frac{x(x+1)}{2}$ floors using this strategy and the building has $k$ floors, we just have to find the minimum value of $x$ such that

$$\frac{x(x+1)}{2} \geq k.$$

Hence,

$$x^2+x-2k=0 \implies x = \frac{-1+\sqrt{1+8k} }{2}.$$

But $x$ must be an integer, implying

$$x =\left\lceil \frac{-1+\sqrt{1+8k} }{2} \right\rceil.$$

In our first example, $k=100$, so plugging it into the previous equation gives $\lceil 13.65\rceil = 14$.

Suppose you have $N$ eggs and you want to determine from which floors in a $k$-floor building you can drop an egg such that is doesn't break. You are to determine the minimum number of attempts you need in order find the critical floor in the worst case while using the best strategy. Now the problem is a bit more complicated because we must find a general solution for any number of eggs and floors. There are three different solutions:

• The recursive solution:
  This solution is more straightforward and can be implemented with ease, but it is also the slowest one. Using this solution on programming contests is not advisable due to its bad performance.

• The dynamic programming solution:
  This solution is similar to the previous one, but it's faster and may be used to solve the problem for medium or small values of $k$ and $N$.

• A solution that combines both binary search and recursion:
  This is the faster one, and once the strategy is understood, it is rather easy to implement.

Imagine the following situation: you have $n$ eggs and $h$ consecutive floors yet to be tested, and afterward you drop the egg at floor $i$ in this sequence of $h$ consecutive floors:

• If the eggs break:
  The problem reduces to $n-1$ eggs and $i-1$ remaining floors.

• If it doesn't break:
  The problem reduces to $n$ eggs and $h-i$ remaining floors. This is an important point. The floors we want to test aren't important; in fact, the number of remaining floors is what matters. For example, testing the floors between 1 and 20 (both 1 and 20 included) would require the same number of drops to test the floors between 21 and 40, or between 81 and 100. In all three situations, we tested 20 floors.

Now we can define a function $W(n,h)$ that computes the minimum number of drops required to find the critical floor in the worst case scenario, whilst using the best strategy.

We can codify the above findings to find the following recursion for determining $W(n,h)$:

Recursion for the egg dropping puzzle:

$$W[n,h]=1+\min\Big(\max \big(W(n-1,i-1),W(n,h-i)\big)\Big)$$

$($Pay attention: $n$=current number of eggs, $N$=total number of eggs, $h$=number of consecutive floors that still have to be tested, $k$=number of floors in the building.$)$

The base cases are as follows:

Because we need $h$ drops if only $1$ egg remains, $W(1,h)=h.$

Because we need only one drop to test one floor, regardless of the number of eggs, $W(n,1)=1.$

Because 0 floors requires no drops, $W(n,0)=0.$

buildingimage

The pseudo-code for this algorithm is given by

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

def drops(n,h):
    if(n == 1 or h == 0 or h == 1):
        return h
    end if

    minimum = ∞

    for x = 1 to h:
        minimum = min(minimum, 
                      1 + max(drops(n - 1, x - 1), drops(n, h - x))
                      )
    end for

    return minimum

C++ code that uses the recursive solution:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

#include <iostream>
#include <limits.h>

using namespace std;

//Compares 2 values and returns the bigger one
int max(int a,int b) {
    int ans=(a>b)?a:b;
    return ans;
}

//Compares 2 values and returns the smaller one
int min(int a,int b){
    int ans=(a<b)?a:b;
    return ans;
}

int egg(int n,int h){

    //Base case
    if(n==1) return h;
    if(h==0) return 0;
    if(h==1) return 1;

    int minimum=INT_MAX;

    //Recursion to find egg(n,k). The loop iterates i: 1,2,3,...h
    for(int x=1;x<=h;x++) minimum=min(minimum,(1+max(egg(n,h-x),egg(n-1,x-1))));

    return minimum;
}

int main()
{
    int e;//Number of eggs
    int f;//Number of floors

    cout<<"Egg dropping puzzle\n\nNumber of eggs:";

    cin>>e;

    cout<<"\nNumber of floors:";

    cin>>f;

    cout<<"\nNumber of drops in the worst case:"<<egg(e,f);

    return 0;
}

The previous solution is very slow, and the same function is called more than once, which is not necessary. However, due to its overlapping subproblems, and to its optimal substructure property (we can find the solution to the problem using the subproblem's optimal solutions), we can solve the problem via dynamic programming.

We can avoid recalculation of the same subproblems by memoizing the function egg(n,h) with a two-dimensional array numdrops[n][h]. Then, we just have to fill it up.

Here's the pseudocode:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

def solvepuzzle(N,k):
    for i = 1 to N
        numdrops(i,1) = 1
        numdrops(i,0) = 0
    end for

    for i=1 to k
        numdrops(1, i) = i
    end for

    for i = 2 to N
        for j = 2 to k 

            numdrops[i][j] = ∞
            minimum = ∞

            for x = 1 to j
                minimum = min(minimum, 
                1 + max(numdrops(i-1,x-1),numdrops(i,j-x))
                )
            end for

            numdrops[i][j] = minimum

        end for
    end for

    return numdrops(N,k)

C++ code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74

#include <iostream>
#include <limits.h>

using namespace std;

//Compares 2 values and returns the bigger one
int max(int a,int b) {
    int ans=(a>b)?a:b;
    return ans;
}

//Compares 2 values and returns the smaller one
int min(int a,int b){
    int ans=(a<b)?a:b;
    return ans;
}

int solvepuzzle(int n,int k){

    int numdrops[n+1][k+1];
    int i,j,x;

    for(i=0;i<=k;i++) numdrops[0][i]=0;
    for(i=0;i<=k;i++) numdrops[1][i]=i;
    for(j=0;j<=n;j++) numdrops[j][0]=0;

    //This loop fills up the matrix
    for(i=2;i<=n;i++){
        for(j=1;j<=k;j++){

            //Defines the minimum as the highest possible value
            int minimum=INT_MAX;

            //Evaluates 1+min{max(numeggs[i][j-x],numeggs[i-1][x-1])), for x:1,2,3...j-1,j}
            for(x=1;x<=j;x++) minimum=min(minimum,(1+max(numdrops[i][j-x],numdrops[i-1][x-1])));

            //Defines the minimum value for numeggs[i][j]
            numdrops[i][j]=minimum;
        }

    }

    cout<<"\nArray:\n\n";

    //Prints numeggs
    for(i=0;i<=n;i++){
        for(j=0;j<=k;j++){
            cout<<numdrops[i][j]<<" ";
        }
        cout<<"\n";
    }

    cout<<"\nNumber of trials in the worst case using the best strategy:\n";

    return numdrops[n][k];
}

int main()
{
    int e;//Number of eggs
    int f;//Number of floors

    cout<<"Egg dropping puzzle\n\nNumber of eggs:";

    cin>>e;

    cout<<"\nNumber of floors:";

    cin>>f;

    cout<<solvepuzzle(e,f);

    return 0;
}

Before advancing to the next section, we must see some useful mathematical relations related to binomials.

We know that

$$C^n_k=C(n,k)= \binom{n}{k} = \frac{n!}{k!(n-k)!}.$$

We also know that the Pascal triangle is

Pascal (image from Wikipedia)

And we can easily find a recursion if we write the Pascal triangle in this way:

Pascal2

By looking at the table or by a simple mathematical proof we get the following recurrence:

$$C ( n , k ) = C( n - 1 , k ) + C ( n - 1 , k - 1 ) .$$

And the base cases are

$$C(n,0) = \frac{n!}{0!(n-0)!} = 1 \quad \text{and} \quad C(n,n )= \frac {n!} {n!(n-n)!} = 1.$$

With this knowledge in hand, let's define a function $f(d,n)$ that represents the number of floors we can cover using $n$ eggs and with $d$ remaining drops. If the egg breaks, we will be able to cover $f(d-1,n-1)$ floors; otherwise we'll be able to cover $f(d-1,n)$ floors. Hence, the total number of floors we will be able to cover is

$$f(d,n) = 1 + f(d-1,n-1) + f(d-1,n) .$$

We must find a function $f(d,n)$ that's a solution for this recursion. First, we will define an auxiliary function $g(d,n)$:

$$g(d,n)=f(d,n+1)-f(d,n) .$$

Plugging it into our first equation gives

$$\begin{aligned} g(d,n) &= f(d,n+1)-f(d,n) \\ &= f(d-1,n+1)+f(d-1,n)+1-f(d-1,n)-f(d-1,n-1)-1\\ &=[f(d-1,n+1)-f(d-1,n)]+[f(d-1,n)-f(d-1,n-1)] \\ &=g(d-1,n)+g(d-1,n-1). \end{aligned}$$

This is precisely the same recursion that we saw in the previous section, and thus the function $g(d,n)$ can be written as

$$g(d,n)= \binom{d}{n}.$$

But we have a problem: $f(0,n)$ is 0 for every $n$, as well as $g(0,n)$, according to the relation between $f$ and $g$. However, a contradiction occurs when $n=0$ because $g(0,0)=\binom{0}{0}=1$. But $g(0,n)$ should be $0$ for every $n$! We can fix this problem by defining $g(d,n)$ as follows:

$$g(d,n)= \binom{d}{n+1}.$$

And the recursion is still valid (you can check it by yourself!).

Now, using a telescopic sum for $f(d,n)$, we can write it as

$$\begin{aligned} f(d,n)= &[f(d,n)-f(d,n-1)]\\ +&[f(d,n-1)-f(d,n-2)]\\ +&\cdots \\ +&[f(d,1)-f(d,0)] \\ +&f(d,0). \end{aligned}$$

We know that $f(d,0)=0$, and therefore

$$f(d,n)=g(d,n-1)+g(d,n-2)+\cdots+g(d,0).$$

And we also know that

$$g(d,n)=\binom{d}{n+1}.$$

Hence,

$$g(d,n-1)+g(d,n-2)+\cdots+g(d,0)=\binom{d}{n}+\binom{d}{n-1}+\cdots+\binom{d}{1}.$$

Finally,

$$f(d,n) = \sum_{i=1}^{n}{\binom{d}{i}} .$$

Now that we have a nice formula for $f(d,n),$ how can we find the minimum number of drops?

It's simple! We know that $f(d,N)$ is the number of floors we can cover in the building with $k$ floors using $N$ eggs and no more than $d$ drops in the worst cases. We simply have to find a value for $d$ such that

$$f(d,N) \geqslant k.$$

Using our last formula,

$$\sum_{i=1}^{N}{\binom{d}{i}} \geqslant k.$$

This solution is very fast. We can do a linear search to find a value for $d$, or we can binary search it for an even faster solution!

C++ code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

#include <iostream>
#include <math.h>

using namespace std;

//Evaluates C(n,k) and verifies if it's greater than or equal to k
long long binomial(int x,int n,int k){

    int i;
    long long int answer=0;
    double aux=1;

    //Calculates C(n,k) using the formula: C(n,k): sum_i_0^k {(n-i+1)/i}
    for(i=1;i<=n;i++){

            aux*=(float)x+1-i;
            aux/=(float)i;
            answer+=aux;

            if(answer>k) break;
    }

    return answer;
}

int main()
{
    int n; //Number of eggs
    int k; //Number of floors

    cout<<"Egg dropping puzzle: ( O(n log k)  solution )\n\n";

    cout<<"Number of floors:";
    cin>>k;

    cout<<"\nNumber of eggs:";
    cin>>n;

    //Binary search variables:
    //Mid: middle
    //Upper: upper limit
    //Inf: inferior limit

    int mid,upper,inf;

    upper=k;
    inf=0;
    mid=(upper+inf)/2;

    //Binary search
    while(upper-inf>1){

        //Finds the middle
        mid=inf+(upper-inf)/2;

        //Define new limits
        if(binomial(mid,n,k)<k) inf=mid;
        else upper=mid;

    }

    cout<<"\nNumber of drops in the worst case:"<<inf+1<<"\n";
}

• Dynamic Programming

• DP solution:

• Solution using binomials: