All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Numbers
Egg drop (Posted on 2002-10-01) Difficulty: 3 of 5
You have two identical eggs, and are given the task of figuring out the highest floor of a 100-story building from which an egg can be dropped safely (meaning that it doesn't break). You have no prior information about this matter, so for all you know a fall from the first floor might break the egg, but then again, it might be strong enough to survive a 100-story drop.

You need to conduct experiments by dropping the eggs from various levels in the building to solve the problem. You are allowed to break both eggs as long as you come up with an answer.

Find a strategy to minimize the maximum number of drops you would have to do. What is this number? (For example if your strategy is dropping an egg from first, then second, then third floors, and so on until it breaks, the maximum number of drops is 100.)

  Submitted by levik    
Rating: 3.8750 (8 votes)
Solution: (Hide)
An efficient stragegy for finding the threshold floor using only two eggs, would be to use the first to establish a range of floors that contains the threshold, and then using the second to pinpoint the actual floor within that range.

So we will throw the first egg off of floors

    X1, X2, X3 ... Xn
until it breaks. Then, if the egg breaks on some attempt number k, we will use the second egg to test floors from 
    Xk-1 + 1 to Xk - 1.

Now our goal is to find the values for Xi that will make our strategy most efficient. Intuitively, it would seem that the ranges of floors should be equal to minimize the needed attempts. However, on further thought, we will see that since higher ranges need more attempts to reach, they should contain less floors, to balance out the total number of attempts used.

The optimal solution is:

    X1 = 14
    X2 = X1 + 13 = 27
    X3 = X2 + 12 = 39
    X4 = X3 + 11 = 50
    X5 = X4 + 10 = 60
    X6 = X5 + 9 = 69
    X7 = X6 + 8 = 77
    X8 = X7 + 7 = 84
    X9 = X8 + 6 = 90
    X10 = X9 + 5 = 95
    X11 = X10 + 4 = 99
With each consecutive range, the range's size is decresed by one, to balance the one extra attempt it will take to get to it. If the first egg fails to break from 99th floor, only one attempt will remain to test if a drop off 100th floor will break it.

Comments: ( You must be logged in to post comments.)
  Subject Author Date
Some ThoughtsPuzzle Thoughts K Sengupta2023-06-10 00:26:53
i think i got itJak Dakars2005-08-22 00:23:27
Some ThoughtsPossible answerEric2003-07-03 15:46:54
re: More thoughtsCheradenine2002-10-02 03:03:16
More thoughtsEnder2002-10-01 12:38:47
fl: explanation attemptCheradenine2002-10-01 07:46:40
re(3):levik2002-10-01 07:46:29
re(2):Cheradenine2002-10-01 07:25:15
Questionre:friedlinguini2002-10-01 07:14:26
Some ThoughtsNo SubjectCheradenine2002-10-01 07:12:09
re: Another thing you could dolevik2002-10-01 06:48:02
Some ThoughtsSolutionEnder2002-10-01 06:46:03
Some ThoughtsAnother thing you could doAeternus2002-10-01 06:25:23
oops only 2 eggsCheradenine2002-10-01 05:58:58
Some ThoughtsNo SubjectCheradenine2002-10-01 05:35:26
 Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (3)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:

blackjack

flooble's webmaster puzzle

Copyright © 2002 - 2024 by Animus Pactum Consulting. All rights reserved. Privacy Information