2 Eggs 100 Floors

You are given two eggs, and access to a 100-storey building. Both eggs are identical. The aim is to find out the highest floor from which an egg will not break when dropped out of a window from that floor. If an egg is dropped and does not break, it is undamaged and can be dropped again. However, once an egg is broken, that’s it for that egg.

If an egg breaks when dropped from floor n, then it would also have broken from any floor above that. If an egg survives a fall, then it will survive any fall shorter than that.

The question is: What strategy should you adopt to minimize the number egg drops it takes to find the solution?. (And what is the worst case for the number of drops it will take?)

Solution:

Ng nal cbvag, vs lbh ner yrsg jvgu bayl 6 rtt, gur bayl fgengrtl gung jvyy tvir lbh gur nafjre vf gb fgneg ng gur ybjrfg haxabja sybbe naq jbex lbhe jnl hc bar-ol-bar hagvy gur rtt oernxf be hagvy lbh ernpu gur gbc sybbe.

Jvgu 7 rttf, lbh pna vzcebir lbhe fgengrtl ol fgnegvat fbzrjurer orgjrra gur ybjrfg haxabja sybbe naq gur uvturfg haxabja sybbe. Vs gur rtt oernxf, lbh pna ryvzvangr nyy hccre sybbef, ohg gura lbh unir gb erireg gb gur 6 rtt fgengrtl. Vs gur rtt qbrfa'g oernx, lbh pna ryvzvangr gung sybbe cyhf nyy sybbef orybj vg, naq gura pubbfr nabgure fgnegvat cbvag nzbat gur erznvavat sybbef naq ercrng.

Jvgu 655 sybbef, lbh pna svaq gur pbeerpg sybbe va 69 qebcf be yrff ol fgnegvat ng sybbe 69. Vs gur rtt oernxf, lbh gura tb gb sybbe 6, jbex lbhe jnl hc, naq jvyy svaq gur pbeerpg sybbe jvgu ng zbfg 69 qebcf. Vs gur rtt qbrfa'g oernx, gura zbir hc 68 sybbef gb 72. Ntnva, vs vg oernxf, lbh jbex lbhe jnl hc sebz 60 naq jvyy svaq gur pbeerpg sybbe va ng zbfg 69 qebcf. Vs vg qvqa'g, lbh zbir hc 67 sybbef, gura 66, rgp. Hfvat guvf zrgubq, lbh pna frr gung lbh jvyy nyjnlf svaq gur pbeerpg sybbe va 69 be srjre qebcf.

Vs lbh nggrzcg gb svaq gur sybbe jvgu 68 be srjre qebcf, lbh pna frr gung lbh zhfg fgneg ng gur 68gu sybbe be ybjre, naq nsgre gur svefg qebc lbh pna zbir ng zbfg 67 sybbef, gura 66, rgp. Lbh jvyy abg ernpu gur gbc bs gur ohvyqvat jvguva 68 qebcf, fb lbh pnaabg thnenagrr lbh jvyy svaq gur pbeerpg sybbe.

Gurersber, nal fgengrtl jvyy va jbefg pnfr erdhver ng yrnfg 69 qebcf.