Hosted by The Math Forum

Problem of the Week 921

The Egg Drop

MacPOW Home || Math Forum POWs || Search MacPOW

Solution:

Answer: 8

The solution uses the fact that 36 is the 8th triangular number, i.e. 36 = 1 + 2 + ... + 8. Here is an algorithm provided by I.P. Sealy (Mount Allison College):

1. Drop the first egg from 8. If it breaks, drop the second egg from 1, 2, ..., 7 as possible.

2. If the first egg doesn't break, drop it from 15. If it breaks, drop the second egg from 9, 10, ..., 14 as possible.

3. If the first egg doesn't break, drop it from 21. If it breaks, drop the second egg from 16, 17, 18, 19, 20 as possible.

4. If the first egg doesn't break, drop it from 26. If it breaks, drop the second egg from 22, 23, 24, 25 as possible.

5. If the first egg doesn't break, drop it from 30. If it breaks, drop the second egg from 26, 28, 29 as possible.

6. If the first egg doesn't break, drop it from 33. If it breaks, drop the second egg from 31, 32 as possible.

7. If the first egg doesn't break, drop it from 35. If it breaks, drop the second egg from 34.

8. If the first egg doesn't break, drop it from 36. If it breaks, the answer is 36 and you have a good egg left.

If there were a 7 dropping solution, then the first drop must be from the 7th floor, the second drop must be from no higher than the 13th floor and so on. This would not reach the top floor.

---

Here is a general solution by Michael Schweitzer (Berlin):

Let d(n) be the minimal number of drops required for a building with n floors. For k  1 let I(k) be the interval of natural numbers [1 + k(k-1)/2, k(k+1)/2].

Claim: If n is in I(k) then d(n) = k.

Proof: For convenience let I(0) := [0, 0]. The claim is true for n = 1. So let n > 1 and assume the claim is true for all numbers less than n. Let n be in I(k). If you drop the first egg from floor f (1  f  n) then either (a) the egg breaks or (b) it does not break. In the first case you have to check floors 1, 2, ..., f-1 (in this order) with the second egg. In case (b) you're in the same situation as in the beginning but with only n-f floors (i.e. two eggs, floors f+1, f+2, ..., n). In the worst case you'll need max[f, 1+d(n-f)] drops and hence d(n) is the minimum over these for 1  f  n. Now observe:

If n is in I(k) then n-k is in I(k-2) or I(k-1). So by assumption d(n-k) = k-2 or k-1, hence max[k, 1+d(n-k)] = k and therefore d(n)  k. If you drop the first egg from a floor f < k then n-f is in I(k-1) or I(k) and hence d(n-f) = k-1 or k and max[f, 1+d(n-f)]  k. If you drop it from a floor f > k then the max is > k. Hence d(n) = k.

Since 36 is in I(8): d(36) = 8 and the proof above can be used to Construct the sequence of floors:

8, 15, 21, 26, 30, 33, 35, 36

[Back to Problem 921]

© Copyright 2000 Stan Wagon. Reproduced with permission.

[Privacy Policy] [Terms of Use]

Home || The Math Library || Quick Reference || Search || Help 

© 1994-2012 Drexel University. All rights reserved.
http://mathforum.org/
The Math Forum is a research and educational enterprise of the Goodwin College of Professional Studies.