Sunday, June 20, 2010

2 eggs and a 100-story building

You are given 2 eggs. You have access to a 100-story building. Eggs can be very hard or very fragile means it may break if dropped from the first floor or may not even break if dropped from 100th floor. Both eggs are identical. You need to figure out the highest floor of a 100-story building an egg can be dropped without breaking. The question is how many drops you need to make in the worst case. You are allowed to break 2 eggs in the process.

You can brute force it by starting at 1 and dropping your first egg until it breaks. This takes 100 drops, 1 egg and a good set of lungs... and maybe a defibrillator...

Since we have 2 eggs we can cut it down by wasting 1 egg first.
So divide and conquer, if we start half way and drop 1 egg. Then if it breaks we have to start at the bottom. However if it didn’t break then we can go up to the 75th floor and try agian. repeating this until we break the egg and then going back to the prior floor that was successful and start dropping the second egg until it breaks. This cuts down the number of drops to less than 50.

However as you can see the problem is when the first egg breaks we are back to the brute force method.

So we need to take it slower with the first egg. So lets start a the 10th floor. we drop the egg and if it doesn't break we go to the 20th floor and repeat. If it breaks we go to the 1st floor and brute force it until the 9th floor. Now consider what happens when the egg brakes on the 99th floor we needed to drop the first egg from the 10th-100th in steps of 10. That's 10 drops. Then we need to drop the second egg 91-99 that s 9 more times for a total of 19 drops in the worst case.

However this worst case happens once. Isnt there a way to make the worst case the same for all combination's and maybe reduce the overall worst case.

So with each drop of the first egg the number of drops we should make for the worst case with the second egg decreases by 1. That way the worst case count is constant. So to figure this out we start from the END at the 100th floor.. that drop will tell us if its 99 or 100 with 1 drop of the second egg at 99 to tell them apart. So the prior drop for the first egg should be at the 98th floor and there would be 2 drops of the second egg after it. Get the picture? So the sequence of eggs drops first then second drops work like this;

First egg(Sequence in reverse) => Second sequence egg if the broke

100 => 99
98 => 96,97
95 => 92,93,94
91 => 87,88,89,90
86 => 81,82,83,84,85
80 => 74,75,76,77,78,79
73 => 66,67,68,69,70,71,72
65 => 57,58,59,60,61,62,63,64
56 => 47,48,49,50,51,52,53,54,55
46 => 36,37,38,39,40,41,42,43,44,45
35 => 24,25,26,27,28,29,30,31,32,33,34
23 => 11,12,13,14,15,16,17,18,19,20,21,22
10 => 1,2,3,4,5,6,7,8,9

And the worst case is now 14

No comments:

Post a Comment