0
$\begingroup$

Recently I've run across the "Two eggs, 100 floors" problem:

You are given two eggs, and access to a 100-story 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.

This page (http://datagenetics.com/blog/july22012/index.html) explains how to solve this puzzle very well, but I've run across an extension that asks for an algorithm for what floor to drop the first egg from.

When considering this for the 2 eggs, 100 floors problem, I found that the first floor to throw the egg from (14) matched the minimum number of throws required to find the floor for which the egg doesn't break from when thrown.

However, when extending this to 3 eggs, the total number of throws needed becomes 9, but that doesn't mean that the FIRST egg throw needs to be made from the 9th floor. Intuitively, it would need to be from a higher floor than 14.

Thus, my question is not "how do you minimize the number of throws" as the original puzzle states. My question is: How do you determine what floor to drop the FIRST egg from when you have n eggs and k floors? Is it possible to find a generalized approach for that?

$\endgroup$
  • $\begingroup$ "How do you minimize the number of throws" - wouldn't it make much more sense to minimize the amount of walking you need to do? Walking up to floor 99 is a lot of work. $\endgroup$ – gnasher729 Nov 13 '16 at 7:43
  • 1
    $\begingroup$ Any reasonable solution to the puzzle would give a complete algorithm, and in particular will tell you where to drop the first egg from. Perhaps the solutions you found aren't good enough. $\endgroup$ – Yuval Filmus Nov 13 '16 at 7:50
  • 1
    $\begingroup$ Assume you have as many eggs as needed. What would be the ideal search algorithm? $\endgroup$ – Raphael Nov 13 '16 at 9:24
  • $\begingroup$ How do you determine what floor to drop the FIRST egg from when you have n eggs and k floors? This is why I never know if this (extended) puzzle isn't math. $\endgroup$ – greybeard Nov 13 '16 at 9:42
  • 2
    $\begingroup$ Possible duplicate of Algorithm to find maximum number of floors you can check with N eggs and D maximum drops $\endgroup$ – David Richerby Nov 13 '16 at 18:51

Your Answer

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

Browse other questions tagged or ask your own question.