Two Eggs Problem

Problem

A building has 100 floors. One of the floors is the highest floor an egg can be dropped from without breaking.

If an egg is dropped from above that floor, it will break. If it is dropped from that floor or below, it will be completely undamaged and you can drop the egg again.

Given two eggs, find the highest floor an egg can be dropped from without breaking, with as few drops as possible.

Solution

Assuming we had only 1 egg, then we cannot take any chances and the only way would be to start with Floor 1 and move up floor-by-floor. If the egg breaks on fall from floor n, then floor n-1 is our answer. so, worst case 100 drops.

Assuming we had infinite number of eggs, then we could use the binary tree stategy and start with floor 50, then floor 25 and that way we will be able to come to the solution in very few drops.

In a 2 egg scenario, we could start with floor 50 and if the egg breaks, then we have no option but to go one floor at a time. so 1+49 chances.

However, we could do better

• Start at floor-10 and drop the egg
  • if the egg does not break, go to floor-20
  • if the egg breaks, go floor-by-floor from floor-1

Repeat this until we find the answer. Worst case being floor 99. 10 + 9=19 drops

Could we do better?

n + (n-1) + (n-2) + (n-3) + .... + 1 >= 100

n(n+1)/2 >= 100

n ~ 14

14		1		13
27		2		12
39		3		11
50		4		10
60		5		9
69		6		8
77		7		7
84		8		6
90		9		5
95		10		4
99		11		3
100		12		0