Why isn't the answer to the "Egg Drop" Problem "no. of floors" or 2?

Question

I've been attempting the "Egg Drop" Dynamic Programming problem however I'm really confused as to why the answer makes sense.

The problem is usually phrased like the follwoing (longer definitions here, here and here among many other places):

You have a number of floors you can drop an egg from. From some floors the egg will be fine when it hits the ground and from others it will break.

Given a certain number of eggs and a certain number of floors what is the minimum number of drops needed to find the threshold floor (the first floor where the egg will break

Apparently the answer to this a of search of the problem space that enumerates out all possibilites and finds the worst case scenario.

This is definitely a case of me not understanding the question, but why is this the answer? To my mind the answer is one of two things:

• If you have 1 egg then it's however many floors you have as you potentially need to drop it from all of the floors (starting from 1). The first one it breaks at is the 'threshold' and this would confirm an answer for you because you know for a fact that every floor beneath it is 'safe'
• If you have n eggs then isn't the answer 2: you drop it and it breaks, then you drop it on the floor below and it doesn't.

Obviously the n eggs answer requires you to get lucky with both drops, but the question is asking for the minimum number of drops needed to find the threshold i.e. the smallest possible number of drops needed to find the answer and confirm it. If you happened to go down this golden path then isn't that answer 2?

As I said, I'm clearly misunderstanding something about the question here - would someone be able to help?

Thanks!

Answer 1

You are indeed misinterpreting the question. When it says:

what is the minimum number of drops needed to find the threshold floor

It means that you must design an optimal strategy that you will apply. The strategy must define from which floor you will do the next drop, based on whether the previous drop broke the egg or not. So it is like a binary decision tree which you follow. Depending on the feedback you get from dropping eggs, you will move in a different direction in that decision tree.

Now you must find the worst case for your strategy: what would be the threshold floor that would take the most drops to find with that strategy?

There are a multitude of strategies. Some of these will need more drops in their worst case scenario, than others. Your job is to find the strategy that minimises the number of drops it needs for its worst case, and to return that number.

Note that what constitutes a worst case for one scenario, might not be a worst case for another. Every strategy has its own worst case.

Be aware: the strategy must never allow you to get into a situations where you have no more eggs left, and still do not know with certainty which is the threshold floor.