31
$\begingroup$

Archeologists discover two dinosaur eggs, and you are given the chance to test the durability of these eggs (bad move on their part). Suppose that these eggs will absorb a specific amount of force with no cumulative damage. In other words, if they don't crack, it is as if they never fell.

You have a 100 story building, and you are allowed only 20 trials.

Questions:

  1. Is there an algorithm such that you can determine the highest floor in which one of these dinosaur eggs can be dropped and not break?
  2. If so, what would be the highest building for which this algorithm would be able to work?
  3. Supposing the number of trials were still 20, but you had as many dinosaur eggs as you needed. At what point would extra eggs not increase the highest floor for which you can test?

Bonus question:

  1. What would be the highest building you could test for with 3 eggs at your disposal?
$\endgroup$
  • 1
    $\begingroup$ To be clear: both eggs are identical, and I do not need to have an unbroken egg at the end of the exercise? $\endgroup$ – oerkelens Nov 18 '14 at 16:05
  • $\begingroup$ @oerkelens Yes, that's correct. $\endgroup$ – Neil Nov 18 '14 at 16:06
  • $\begingroup$ Is the building structure such that you can drop an egg from one floor to a lower one which isn't the ground floor? If so, does each time of doing this count as one trial or can you drop (6th)->(4th)->(3rd) in a single trial? $\endgroup$ – Rand al'Thor Nov 18 '14 at 16:06
  • $\begingroup$ @randal'thor I didn't consider that possibility, though I suppose you could. Though yes, it would count as a trial and dropping from the 6th floor to the 4th is the same as the 3rd floor to the 1st (ground) floor in that you've only proven the egg can fall 2 stories without breaking (assuming of course that it doesn't break). $\endgroup$ – Neil Nov 18 '14 at 16:08
  • $\begingroup$ Damn - so that loophole doesn't work! $\endgroup$ – Rand al'Thor Nov 18 '14 at 16:17
44
$\begingroup$
  1. Take the first egg. Drop it from floors 10, 20, 30, ..., 100 until it breaks. This will take at most 10 of the 20 trials. When it breaks, go 9 floors down, and test every floor with the remaining egg. E.g. if the first egg breaks at 70, drop the second egg from 61, 62, 62, ..., 69. That's at most 19 trials in total.

  2. We can do a bit better though. If the first egg breaks on the first trial, we've got 19 trials left, so we can actually drop it from the 20th floor right away, because there are enough remaining trials to test each floor below. If it doesn't break, we can go 19 floors up for the second trial (with the same egg). Continuing like this, we might be lucky to be using the first egg for all 20 trials without risking not having enough trials to figure out the exact floor. This means we can go up to 20 + 19 + 18 + ... + 1 = 210 floors, using

This:

$$ \sum_{n=0}^{19} n+1 = \sum_{n=1}^{20} n = \frac{20(20+1)}{2} = 210. $$

Just to break down the first version of this:

There are 20 possibilities for when the first egg breaks. For each case $n$ is the number of trials left. And for each such case we can test $n$ floors with the second egg and $1$ floor with the egg we potentially broke. Hence the summand of $n+1$.

  1. With more eggs, you can can basically apply a binary search, halving the potential range of floors each time. That lets you check 220 = 1048576 floors. The first egg is dropped from floor 219, then you go up or down 218 floors depending on whether the egg broke on the first trial.

  2. With three eggs, we can test considerably more than with two eggs. Consider the first egg breaking on the first trial. Then we've got 19 trials and two eggs left. Applying algorithm 2, we can still test 190 floors with those. So we can drop the first egg from floor 191. If the first egg breaks on the second trial, we've still got 18 trials and two eggs left, with which we can test 171 floors, so we can make the second trial already from floor 373, and so on. This holds as long as there are at least two trials left, so that we can make use of both eggs. If we're still dropping the first egg on trial number 19, then we've only got one trial left, so we can only go up two floors for the 19th trial. I think this coincides with the previous formula, but I'm not sure it would if we generalise this beyond 3 eggs. Basically, for the last two trials, this reduces to the above formula.

So we have with 3 eggs:

$$ \sum_{m=1}^{18}\left(1+\sum_{n=0}^m n+1\right) + \sum_{n=0}^{1} n+1 = 1350 $$

$\endgroup$
  • $\begingroup$ Why do you need to use 2 eggs at a time, in #3? $\endgroup$ – Andrea Gottardi Nov 18 '14 at 16:21
  • 1
    $\begingroup$ About number 3, why isn't it 2^20 (or 2^19) floors? you put on a binary search, so you can halve with a single egg $\endgroup$ – Andrea Gottardi Nov 18 '14 at 16:34
  • $\begingroup$ @AndreaGottardi yeah, I kinda assumed I'd have to check the upper end of each interval again, but that's useless. $\endgroup$ – Martin Ender Nov 18 '14 at 16:35
  • $\begingroup$ @MartinBüttner I'm honestly not even sure that the 4th answer is correct, but it seems you're going about it right. You did Sum of 1 to 20 + sum of 1 to 19 + sum of 1 to 18, etc.? $\endgroup$ – Neil Nov 18 '14 at 16:49
  • $\begingroup$ @Neil +1 each time (because I can go one higher than the numbers of floors I test with the remaining two eggs). But the sum might be off for the last one or two trials, I'll rethink that. $\endgroup$ – Martin Ender Nov 18 '14 at 16:49
12
$\begingroup$

We can do it with at most 14 trials. 1st drop from 14th floor. If the egg breaks we can with the second egg determine the intermediate floor with at most 13 more trials (starting from 1st and moving one floor up at the time). If first egg does not break after throwing it from 14th,we re-drop it from 27th (14+13=27).If it breaks ,we determine the intermediate floor with still 12 trials at most. If not break from 27th ,re-drop from 39th. (14+13+12)......11 more trials otherwise.

The procedure repeats as above. If generally 1st egg breaks at n-th drop we will still need at most another 14-n drops with the second egg. If we reach 11th repeat of procedure we will be at floor 99

Mathematical explanation: 1+2+3+4+...+14=105

$\endgroup$
  • $\begingroup$ I think the idea is solid, but why 14 trials? You have 20 at your disposal. $\endgroup$ – Neil Nov 18 '14 at 16:33
  • $\begingroup$ Yes. 1+2+3+...+20= 210 maximum $\endgroup$ – George R. Nov 18 '14 at 16:38
  • $\begingroup$ I'm not sure I follow. 14 trials because the sum of 1 through 14 is half of 210? $\endgroup$ – Neil Nov 18 '14 at 16:40
  • 3
    $\begingroup$ Neil, One can "cover" 100 floors with at most 14 trials. The reason was explained at my answer, wasn't it? $\endgroup$ – George R. Nov 18 '14 at 16:46
  • $\begingroup$ 14 trials is all that is required to test given the original 100-story building, because the sum of the number of floors that you can increase on each test forms a triangular number, which you can calculate as n(n+1)/2. The 14th triangular number is 105, so given 14 trials you can test using the entire 100-story building. $\endgroup$ – KeithS Nov 18 '14 at 16:50
3
$\begingroup$

As mentioned in another answer, I would use the first egg to incrementally test as far UP as I can go while still having enough remaining trials to test the skipped floors. Basically test 1 is go up 20 floors, if the egg breaks, start at the bottom floor and begin testing upwards one floor until you find the breaking point. If the egg did NOT break at floor 20, I would go up an additional 19 floors and test again. Use the remaining 18 trials to test floors 21 - 39.

Continue moving up by the number of trials remaining until the first egg breaks, then go back to the bottom of your test set and work your way up.

To determine the largest building that this method will work you must simply do

20+19+18+17+16+15+14+13+12+11+10+9+8+7+6+5+4+3+2+1 = 210 stories.

For the second part of the questions, given an unlimited number of eggs, the answer is to use the divide and conquer method. Given 100 floors, start at the "middle" floor and test up or down reducing the trial size by 1/2 each test.

If egg breaks, repeat from floor 25. If egg is intact, move up to floor 75. Continue to test from the half ways points until you have determined the correct floor.

E.G. Presuming that the answer was that the egg tolerated being dropped from the 88th floor without breaking (out of 100).

TRIAL 1 - drop from 50th floor -> No break, retest only top half TRIAL 2 - drop from 75th floor -> No break, retest only top half TRIAL 3 - drop from 87th floor -> No break, retest only top half TRIAL 4 - drop from 93rd floor -> break, retest only bottom half TRIAL 5 - drop from 90th floor -> break, retest only bottom half TRIAL 6 - drop from 88th floor -> No break, can be dropped from up to 88 floor TRIAL 7 - drop from 89th floor -> break, 88 is the answer.

Another Example, Presuming that egg can only be dropped from the first floor without breaking. (second story breaks egg)

TRIAL 1 - drop from 50th floor -> break, retest only bottom half TRIAL 2 - drop from 25th floor -> break, retest only bottom half TRIAL 3 - drop from 12th floor -> break, retest only bottom half TRIAL 4 - drop from 6th floor -> break, retest only bottom half TRIAL 5 - drop from 3rd floor -> break, retest only bottom half TRIAL 6 - drop from 2nd floor -> break, retest only bottom half TRIAL 7 - drop from 1st floor -> no break, floor 1 is the answer.

The largest size building is equal to the largest number that can be divided into equal parts not having more than 3 floors in the final two trials. A building with 2048 floors could be tested with only 11 trials.

Following this logic the largest size building you could test with this method is 1048576 stories tall.

The point at witch additional eggs becomes irrelevant is at 20, since the number of trials limits the number of "splits", not the eggs.

Bonus question:

Having three eggs at your disposal increases the size of the building that you can test substantially because you can blend the two methods mentioned above.

You would begin at whichever floor is the highest that you can go so that you only need to test 1/2 of the floors with the remaining trials.

TRIAL 1 test from floor 38. If the egg breaks, use the second egg to test at floor 19. If the egg breaks use the third egg to systematically test floors 1-18; if it doesn't break use the third egg to test floors 19-37.

Repeat incrementing up double the one less than the number of floors that you have trials remaining.

Thus the maximum number of floors is 38+36+34+32+30+28+26+24+22+20+18+16+14+12+10+8+6+4 = 336 floors with 3 eggs.

Personally, speaking I must say that I would only test two stories since I'd really just enjoy having the excuse to throw eggs at people as they walk by and since my aim isn't that good, I'd throw both eggs from the second story to increase my chances of hitting someone.

$\endgroup$
2
$\begingroup$

Martin Buttner has already answered the question as stated, but as a pure mathematician I feel obliged to generalise.

If you're allowed $kn$ trials and you have $k$ eggs, then the maximum number of floors for which you can test using Martin's method is $n^k$.

Is this algorithm best possible?

$\endgroup$
  • $\begingroup$ No, because the highest possible number of floor for which you can test is higher. It is $n^k$ for @Martin's answer only. $\endgroup$ – Neil Nov 18 '14 at 16:25
  • $\begingroup$ @Neil Isn't that what he said? $\endgroup$ – Scimonster Nov 18 '14 at 16:25
  • $\begingroup$ @Scimonster That it wasn't optimal? $\endgroup$ – Neil Nov 18 '14 at 16:27
  • 1
    $\begingroup$ Whew! @Martin's new method is going to be harder to generalise... $\endgroup$ – Rand al'Thor Nov 18 '14 at 17:05
1
$\begingroup$

Yes, dropping it from the 10th, 20th floor etcetera is nice, but I need a maximum of 9 trials after that (1-9).

So how about I drop my first eg from floor 11, then 22, etc. When It drops, I go back 10 floors and in a maximum of ten tries I have my answer.

So the answer to question 1 is yes.

However, the answer to the second question is not 100, but 120 (!!!) floors: I can move up 11 floors ten times, and still have ten tries for the second egg. If I am at floor 110 and my first egg does not break, I can still use ten tries to try floor 111-120.

$\endgroup$
  • $\begingroup$ Sorry, edited by now, and I'm up to 210. ;) $\endgroup$ – Martin Ender Nov 18 '14 at 16:34
0
$\begingroup$

Well, assuming the eggs aren't made of titanium alloy, the simplest way would be to

start on the first (or second) floor, drop the egg, then move up a floor, repeat, until one of the eggs breaks. The floor below the one where it broke is obviously the highest height it could fall from. This will get you up to a height of 200 feet from the 20th floor of the building. Not many organic things can survive a 200-foot fall onto a hard surface.

If the eggs appear to be made of sterner stuff, you could significantly increase the maximum test height by

going in twos; start on the second floor, drop the egg. If it doesn't break, move to the fourth floor and try again, repeating until the egg breaks (or you have exhausted 19 trials, getting you to the 38th floor). Once you get a break, move down one floor and drop the other egg. If that egg breaks, the maximum height is one floor below (the last height at which you dropped the first one safely). If it doesn't, you're at the maximum height for a safe egg drop. If the egg has survived a drop from the 38th floor, your final test can either move up one story or two. If a drop from the 39th floor breaks, you know exactly how high you can drop the egg from (the 38th floor). If that drop doesn't break, the best you know is that the dino egg will at least survive a 39-story fall. If you move to the 40th floor, the solution becomes ambiguous if the egg breaks; you are out of trials to determine whether a 39-story fall is survivable.

Depending on the required accuracy of the result, you could also

do the same thing in threes. Start on the third floor, and if the egg doesn't break, move to the sixth, until you get a break (or have exhausted 19 of the 20 trials on the 57th floor). Then move down one floor and try again. If the egg doesn't break, you're at the maximum height. If it does break, the maximum height is somewhere in the ten feet between the story below (which you can no longer test) and the one below that (which you tested safely with the first egg). Ten feet, all told, is a pretty narrow window of uncertainty; it's less than 2% error given the maximum height you can test in this way is 540 feet.

With unlimited eggs, the solution's pretty easy:

Binary search. Start at the 50th floor, drop an egg. If it doesn't break, move to the 75th and try again. If it does break, move to the 25th. Depending on whether that drop breaks, move 12 floors up or down, then 6, then 3, then 1, until you have dropped from three consecutive floors, at least one of which has not broken and one of which has. The maximum height supported by 20 trials (and a max of 20 eggs) would be a staggering 2^20 = 1,048,576 floors, over 10 million feet in the air (at which point you're dropping the egg from beyond low Earth orbit, at 1,985 miles from Earth's surface)

$\endgroup$
  • $\begingroup$ They are dinosaur eggs. I am fairly sure that the assumption they will break before floor 20 or 50 is as unfounded as the assumption they will not break from floor 68. $\endgroup$ – oerkelens Nov 18 '14 at 16:36
  • $\begingroup$ Surely you could test beyond the 20th floor with 2 eggs. $\endgroup$ – Neil Nov 18 '14 at 16:37
  • $\begingroup$ You can; see my other solutions. You can test to the 39th floor if you need an exact answer, and to the 56th floor if you are willing to accept a one-story possible window instead of an exact answer. But, George R's answer is better there. My answer to unlimited eggs is the correct one so I'll keep it here. $\endgroup$ – KeithS Nov 18 '14 at 16:42
0
$\begingroup$

To all you saying the answer to #3 is 2^20, let's simplify it to two trials. You can only do 3 floors with two trials. There are four options. Breaking at the first, second, third floor, or not at all.

The answer is 2^20-1

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.