Dropping eggs

Eggs

Imagine you're a farmer and you've produced a breed of hen that lays particularly strong eggs. You want to test just how strong those eggs are by throwing them off the various floors of a 100-story building. Your task is to find the highest floor you can drop an egg from without breaking it. If you had just one egg, you'd know how you would do this: first throw the egg off the 1st floor, if it doesn't break move up to the second, then the third, and so on. You'd need at most 100 throws to find the answer.

But now suppose you had two eggs. What strategy would you use to find the highest drop an egg can survive? What's the smallest number of egg throws you can get away with?

It's been claimed that this puzzle has been used by Google and/or Microsoft as a job interview question for computer programmers. We came across it on Wild Maths, a website that encourages students to explore maths beyond the classroom and is designed to nurture mathematical creativity. Visit Wild Maths for this and other puzzles and challenges.

Comments

I would start at floor 2, drop an egg, if it survives move to floor 4 and repeat, if successful keep moving up the floors two at a time. Then when an egg breaks, go down one floor and drop the other egg. This method would take at most 51 throws.

Wondered what would happen if you went up several floors at a time. Serendipity had it that I started at the tenth floor, ascending another ten if the egg didn't break and testing at each of the previous nine floors if it did. Turns out to be 19 tests - which appears to be a minimum. After playing around in Excel and resurrecting 40 year old calculus:

In general for a building with F floors, split into N stages of x floors the number of tests T required are: T = N + x - 1

N = F/x so T = F/x + x -1 with derivative dT/dx = 1 - F/x^2; giving a minimum at x = sqrt(F)

For 100 floors the minimum is at 10 and 19 tests are required.

With the following method it take max 14 trys (to reach every floor up to 100).

1. Test from floor 14.
If it fails, test with second egg the floors from 1 to 13 until the second egg breaks.
It will take max 13 further trys to test from all floors below 14.
==> 1 test (first egg) + max 13 tests (second egg) <= 14 tests.

2. If the first test is positive, test from floor 27 (14+13).
If it fails, test with second egg the floors from 15 to 26 until the second egg breaks.
It will take max 12 further trys to test all floors betwee 15 to 26.
==> 2 tests (first egg) + max 12 tests (second egg) <= 14 tests.

3. If the second test is positive, test from floor 39 (14+13+12).
If it fails, test with the second egg in the same way as in 1. and 2. for floors 28 to 38.
==> 3 tests (first egg) + max 11 tests (second egg) <= 14 tests.

4. If the third test is positive, test from floor 50.
If it fails, test with the second egg from the floors 40 to 49.
==> 4 tests (first egg) + max 10 tests (second egg) <= 14 tests.

5. If the fourth test is positive, test from floor 60.
6. If the fifth test is positive, test from floor 69.
7. If the sixth test is positive, test from floor 77.
8. If the seventh test is positive, test from floor 84.
9. If the eighth test is positive, test from floor 90.
10. If the ninth test is positive, test from floor 95.
11. If the tenth test is positive, test from floor 99.
If it fails, test with the second egg from the floors 96 to 98.
==> 11 tests (first egg) + max 3 tests (second egg) <= 14 tests.

12. If the elevenths test is positive, test finally from floor 100.
==> 12 tests (first egg) + no test (second egg) = 12 tests.

I got 34 as the minimum.

First, you test floor 3.
-If it breaks, try floor 1.
-If it doesn't break at 1, try floor 2.

Second, you test floor 6.
-If it breaks, try floor 4.
-If it doesn't break at 4, try 5.

Using this by three-method, you will get up to 99 throwing it 33 times(100 divided by 3=33r1) then you have to do it just one more time for the 100th floor, so 33+1=34, and then you're done!!!!!

I would first drop from floor 1, if it didn't break I'd drop my second egg from floor 100. If it broke I'd drop my third egg from floor 50. If the third egg didn't break I'd drop from floor 75, if the third egg did break I'd drop from floor 25, and so on.

Brandon

Babes, there are only two eggs.