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.
dropping eggs
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.
?
Good choice!
Good job
In all honesty I would do the exact same as you
Dropping Eggs - Fewer than you might think.
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.
14 trys
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.
Dropping eggs
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!!!!!
Egg drop by halves
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
Babes, there are only two eggs.
Egg Drop
You would start from the first floor with one egg and test if it broke then if it didn't break you would retrieve it and repeat on the 2nd floor etc. until it broke then you would test from the same floor with the second egg and if that didn't break you would just continue but if it did break you would know that that is the maximum height you can throw it from without it breaking
Dropping eggs
The easiest way to do this is to start from the first base and drop the egg. If it doesn't break, go to the next site. If it breaks, then the maximum site of egg survival is 0.
@_@
Logically the eggs will break from the first floor
So no need to waste the egg or the time ....
dropping eggs
Drop the first one at floor 50. If it does break start with the second egg at floor 1 and work up from there until it breaks. If it doesn't break take the first egg and drop it from floor 75. If it does break take the second egg and start working upwards from floor 51 until it breaks. If it doesn't break drop the first egg from floor 88. If it breaks from Floor 88 take the second egg and drop it from floor 76 and work up from there until it breaks. If the first egg doesn't break from floor 88, take it up to floor 94 and drop it from there. If it breaks take the second egg and drop it from floor 89 and work up from there until it breaks. If it doesn't break take the first egg and drop it from floor 97....no, chances are it will be good for floor 100 and go from there :)
Egg Drop
I believe the minimum number of drops is 4.
Divide the 100 by 3, drop at 33 and 66 (one floor over, include it later. 33 floors each drop)
Divide the survival “third” by 3, drop at first 3rd and second 3rd (11 floors on each drop)
Divide the survival third by 3, drop at first 3rd and second 3rd (3 floors each drop)
Drop egg on the second and 3rd floor of the identified floors. This gives the answer.
Dropping Eggs
Revised numbers from my previous submission.
The answer is 4 drops, 2 eggs each time giving 8 eggs.
So that’s 4 drops using 8 eggs.