Problem of the Week

Week of February 4, 2019

Friday, February 8, 2019

Problem: You are given 2 identical eggs and access to a 100-story building. Eggs can be very hard or very fragile which means they may break if dropped from the first floor or may not even break if dropped from 100th floor. What is the worst case minimum number of drops to determine the highest floor of the 100-story building an egg can be dropped from without breaking?

Hint: With 1 egg left and n floors left to check, it would take n drops in the worst case. Now suppose x is the optimal worst case minimum...

Solution: Suppose x is the optimal worst case minimum. Then the best we can do is to make the first drop on floor x, since if the egg breaks we have x-1 more floors to check with 1 egg. But if the egg doesn’t break we have used up one trial, so the best we can do now is to drop from floor x+(x-1), since if the egg breaks we have x-2 trials to check the x-2 floors that remain in doubt, and so on. Thus we must have x+(x-1)+...+1 = x(x+1)/2 be at least 100 and the smallest such integer x is 14.

Contact:

Maria Cristina Manabat
tmanabat@sandiego.edu
(619) 260-4706

College of Arts and Sciences

Contact Us Email

Phone: (619) 260-4600
Fax: (619) 260-4162
casinfo@sandiego.edu

Visit Campus Map

Founders Hall
5998 Alcalá Park
San Diego, CA 92110