Skip to content

Three eggs, nine drops: tallest building

Question

You hold 33 identical eggs in a building with nn floors. There is an unknown critical floor XX with 1≤X≤n1\le X\le n: an egg dropped from below floor XX survives undamaged, and an egg dropped from floor XX or higher breaks. It is known that eggs break from the top floor nn. What is the largest nn for which you can always determine XX using no more than 99 drops?

Short answer

130. With ee eggs and dd drops you can distinguish ∑k=0e(dk)\sum_{k=0}^{e}\binom{d}{k} possibilities: the first drop splits the problem into (e−1,d−1)(e-1,d-1) below and (e,d−1)(e,d-1) above. For e=3,d=9e=3,d=9 this is 1+9+36+84=1301+9+36+84=130, so XX can be found among up to 130130 floors. Practically, first drop from floor 3737 (since two eggs and 88 drops cover 3636 floors), then step up by 29,22,…29, 22,\dots

Adapted from QuantQuestions.io; question and answer rewritten by SelfMadeQuant.com.

See the hint and the full worked solution in the question bank (free account).

Open the worked solution