Two Eggs

The most obvious methods are linear and binary search. However, a linear search would require on average $\frac{100}{2}=50$ drops, and a binary search would require on average $\frac{100}{4} = 25$ drops, since we can only afford to partition the $100$ floors once with two eggs.

Instead, we might try to start at the tenth floor and work our way up in multiples of ten. Once the first egg breaks, we go back to the previous floor and perform a linear search with the second egg. Then, if the egg cannot be dropped from above the 11th floor, for example, the problem would be solved after three tests: DROP(10), DROP(20), DROP(11). However, if the egg is on the 99th floor, the ten-floor-partition method requires 18 drops: DROP(10), DROP(20)...DROP(90), DROP(91)...DROP(99).

This gives an average of 10.9 drops, as demonstrated by averageDrops.java :

 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

public class averageDrops
{
    public static void main(String[] args)
    {
        int sum = 0;
        for (int i=1; i<=100; i++)
        {
            sum += drops(i);
        }
        System.out.println(sum/100.0);
    }
    public static int drops(int floor)
    {
        int numDrops = 0;
        int currentLevel = 1;
        for (int i=10; i<floor; i+=10)
        {
            currentLevel = i;
            numDrops++;
        }
        numDrops++;
        for (int j=currentLevel; j<floor; j++)
        {
            numDrops++;
        }
        return numDrops;
    }
}

However, if our first egg survives a drop from the $n$ th floor, we can then move up $n-1$ floors to ensure a maximum of $n$ tests. To minimize the total number of drops, let $n+(n-1)+(n-2)+...+1 \ge 100$ . Solving for $n$ , we find $\frac{n(n+1)}{2} \ge 100 \implies n=14$ , since $n$ must be an integer.

Then, averageDrops2.java gives a value of 9.68:

 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

public class averageDrops2
{
    public static void main(String[] args)
    {
        int sum = 0;
        for (int i=1; i<=100; i++)
        {
            sum += drops(i);
        }
        System.out.println(sum/100.0);
        System.out.println(drops(14));
    }
    public static int drops(int floor)
    {
        int numDrops = 0;
        int currentFloor = 14;
        final int START = 14;
        for (int i=1, j=14; i<14 && j<floor; i++, j+=(START-i))
        {
            currentFloor = j;
            numDrops++;
        }
        numDrops++;
        for (int i=currentFloor; i<floor; i++)
        {
            numDrops++;
        }
        return numDrops;
    }
}

Therefore, it is best to start on the $\boxed{14}$ th floor.

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

import Data.List
import Data.Ord (comparing)
import qualified Data.Vector as V

res n = vec V.! n
    where
        vec = V.fromList [g i | i <- [0..n]]
        -- g n - returns number of drops for building with n floors
        -- vec used to memorize values of g
        g 0 = (0, 0) -- (starting floor, number of drops)
        g 1 = (1, 1)
        g i = minimumBy (comparing snd) [(k, max k (1 + snd (vec V.! (i-k)))) | k <- [1..i]]

print $ res 100

The answer is not unique. Floors from 9th to 14th are all equally good. Starting with any one of them, you can acheive minimal number of drops that is 14.

An illustration of non-uniqueness for a building with 4 floors only:

Drop 1st egg from 1st floor : If it broke you are done, if not you will have to start dropping 2nd egg going up from 2nd floor up to 4th (in the worst case).

Worst case: 4

Drop 1st egg from 2st floor : If it broke, you will have to check one more floor below. 2 drops total. If it survived, you will have to check two floors above. 3 drops in the worst case.

Worst case: 3

Drop 1st egg from 3rd floor : If it broke, you will have to check two floors below. 3 drops total in the worst case. If it survived, you will have to check one floors above. 2 drops.

Worst case: 3

Drop 1st egg from 4th floor : If it broke you are done, if not you will have to check three floors below.

Worst case: 4

Starting either from 2nd or 3rd floor, you can acheive the minimal number of drops 3.

A brilliant link explaining egg-dropping problem (without code) : Nigel Coldwell Puzzle 60

You can drop from floors 12 or 13 as well. There are many optimal solutions. 14 is the most obvious solution, but 12 or 13 are more appealing for the first drop if you really don't like climbing stairs.

For example,

12, 25, 37, 48, 58, 67, 75, 82, 88, 93, 97, 100

First attempt must be from floor 14, then continue dropping it from mutiple of 14-n (0 to 13), you will findout the floor from which egg is broken. Min 14 floor

number of floors=100 number of eggs=2 minimum step in worst case=14 Process: pick 9th floor and drop the egg if egg breaks: eggs remaining:1 floors to check:->1->2->3->4->5->6->7->8 if egg doesn't break: pick 22th floor and drop the egg if egg breaks: eggs remaining:1 floors to check:->10->11->12->13->14->15->16->17->18->19->20->21 if egg doesn't break: pick 34th floor and drop the egg if egg breaks: eggs remaining:1 floors to check:->23->24->25->26->27->28->29->30->31->32->33 if egg doesn't break: pick 45th floor and drop the egg if egg breaks: eggs remaining:1 floors to check:->35->36->37->38->39->40->41->42->43->44 if egg doesn't break: pick 55th floor and drop the egg if egg breaks: eggs remaining:1 floors to check:->46->47->48->49->50->51->52->53->54 if egg doesn't break: pick 64th floor and drop the egg if egg breaks: eggs remaining:1 floors to check:->56->57->58->59->60->61->62->63 if egg doesn't break: pick 72th floor and drop the egg if egg breaks: eggs remaining:1 floors to check:->65->66->67->68->69->70->71 if egg doesn't break: pick 79th floor and drop the egg if egg breaks: eggs remaining:1 floors to check:->73->74->75->76->77->78 if egg doesn't break: pick 85th floor and drop the egg if egg breaks: eggs remaining:1 floors to check:->80->81->82->83->84 if egg doesn't break: pick 90th floor and drop the egg if egg breaks: eggs remaining:1 floors to check:->86->87->88->89 if egg doesn't break: pick 94th floor and drop the egg if egg breaks: eggs remaining:1 floors to check:->91->92->93 if egg doesn't break: pick 97th floor and drop the egg if egg breaks: eggs remaining:1 floors to check:->95->96 if egg doesn't break: pick 99th floor and drop the egg if egg breaks: eggs remaining:1 floors to check:->98 if egg doesn't break: pick 100th floor and drop the egg if egg breaks: no need to check if egg doesn't break: no need to check This is my code's solution prove this is wrong or make answer 9 as accepted.