Three eggs and a hundred floors

Question

A building has 100 floors. There is a critical floor: eggs dropped from that floor or higher break, eggs dropped from below it survive (and can be reused). You have three identical eggs. What is the smallest number of drops that guarantees you can identify the critical floor, whatever it is? Explain the reasoning and how it generalises from the two-egg case.

Accepted Answer

Nine drops. Count the floors you can handle. Let F(d, e) be the largest number of floors that d drops and e eggs can handle. Drop the first egg from some floor. If it breaks, you must finish with d minus 1 drops and e minus 1 eggs on the floors below, so that floor can be at most F(d minus 1, e minus 1) + 1. If it survives, you have d minus 1 drops and e eggs for the floors above: F(d minus 1, e) more floors. So F(d, e) = F(d minus 1, e minus 1) + 1 + F(d minus 1, e), with F(0, e) = 0 and F(d, 1) = d (one egg forces floor-by-floor testing). Closed form. With two eggs this gives the triangular…

Three eggs and a hundred floors

Your answer

Discussion

Learn the concepts

Related questions