2 eggs 100 Floors

[rbrown]

Any help appreciated -

You are given 2 eggs. You have access to a 100-storey 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 100 th floor.Both eggs are identical. You need to figure out the highest floor of a 100-storey building an egg can be dropped without breaking. Now the question is how many drops you need to make. You are allowed to break 2 eggs in the process

 

[Andy_B]

This is just a guess, but I don't see how this could be done in less than 19 drops. The first egg you take to each multiple of ten (10, 20....) and once it breaks you use the other egg one floor at a time. Thus if it is the 99th floor you will have ten drops with one egg and nine with the second. Wouldn't be surprised if there's a better answer out there though.

 

[TBeas]

That's easy. Eggs break from any fall greater than 2 meters.

 

[RedPanda]

This is just a guess, but I don't see how this could be done in less than 19 drops. The first egg you take to each multiple of ten (10, 20....) and once it breaks you use the other egg one floor at a time. Thus if it is the 99th floor you will have ten drops with one egg and nine with the second. Wouldn't be surprised if there's a better answer out there though.

So, if the egg break on the 10th floor, you have 1+9=10 drops total. If it doesn't and you move to 20th floor you face one extra drop. In this case, you need to move not 10, but only 9 floors higher and so on... Obviously, you cannot start from 10th floor in this case, but you can check that if you start at 14th floor, you can do it with 14 drops only.

 

[Andy_B]

Wow, crazy I didn't see that, it seems so obvious now (of course!).

 

[CN Chen]

Generalized
F = D * (D+1) / 2

where:
F is the maximum number of floors supported
D is the number of drops

 

[IlyaKEightSix]

Hmmm...this problem would be rather simple if not for the constraint of only being allowed to break two eggs. But that aside, wouldn't a simple binary search work?

Drop both eggs from the nth/2 floor, if both break, drop both from the nth/4 floor, and continue cutting in half the amount of space you inspect from which to drop the hardest egg.

That said, there's probably some optimization given this constraint of only dropping two eggs by punishing higher floors so you start at some lower value, then depending on when the harder egg breaks, you take it from there.

 

[Lyosha]

But that aside, wouldn't a simple binary search work?

No.

Well, perhaps, in a cumbersome way... But do the math.

 

[lordvid]

Any help appreciated -

You are given 2 eggs. You have access to a 100-storey 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 100 th floor.Both eggs are identical. You need to figure out the highest floor of a 100-storey building an egg can be dropped without breaking. Now the question is how many drops you need to make. You are allowed to break 2 eggs in the process

Assuming you don't can break as many eggs as you want, you need to make a minimum of ceil(log_2_100) = 7 drops.

But because you can only break 2...then you can get an exact floor height only for some cases....

For example, if the max height is 99...you break the egg dropped from the 50th floor, then drop from the 75th, 88th, etc...until you drop from the 1ooth and the egg is broken.

If the max height is 1, you drop from 50th--broken.....you drop from 25th--broken...you can only conclude that 1 <= max height <= 24.

If the max height is 49th or 48th...you can figure out exactly too .... and so on....


Edit: Actually, for the ones where you can get the exactly floor, you may be able to do it in 6 drops....by only dropping from the higher of the 2 remaining floors and concluding from there...

 

[benzbubblecat]

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 100 th floor.

You need to figure out the highest floor of a 100-storey building an egg can be dropped without breaking.

Are we trying to find the specific floor number for the two identical eggs we have (had, after we break both) or are we trying to generalize a rule for "an egg" which "may break if dropped from the first floor or not even break of dropped from the 100th floor"?

 

[CChow]

CN Chen has the right answer above. This is really a great question, I like it quite a bit.