# Thread: trouble understanding a part of the egg dropping puzzle

1. ## trouble understanding a part of the egg dropping puzzle

Hello,
I have been thinking about this part of the egg dropping puzzle now for a couple of days, but haven't been able to come up with a reason.

I don't understand why,if the egg doesn't break when dropped some floor n, the next time, rather than jumping up another n floors, instead we step up just (n-1) floors and then (n-2), (n-3) and so on.

One of the sites I was referring to says, it's because we have one less drop available if we have to switch to one-by-one floors, so the next floor we should try is floor n + (n-1). Similarly, if this drop does not break, we next need to jump up to floor n + (n-1) + (n-2), then floor n + (n-1) + (n-2) + (n-3) … We keep reducing the step by one each time we jump up, until that step-up is just one floor, and get the following equation for a 100 floor building
n + (n-1) + (n-2) + (n-3) + (n-4) + … + 1 >= 100

Just to reiterate, my question is, why in the subsequent iteration, the number of floors is n-1.

Web link I was referring to is this

Thanks.

2. ## Re: trouble understanding a part of the egg dropping puzzle

It is subtracted by 1 because you are doing some "load balancing".

A perfectly balanced system is one where the total number of drops (for both eggs) is constant, regardless of where the first egg breaks. For that to be the case, each additional drop the first egg takes, reduces the number of potential drops the second egg can make.

So, for example, if the algorithm is to drop the first egg at floor 20, then the number of potential drops the second egg has is 19. So, when we drop the first egg again, we need to reduce the number of potential drops of the second egg to 18. Thus, we drop the first egg at floor 20, then floor 39.

That then gives rise to solving for $n$ such that $\sum_{i=1}^{n}i=100$.

3. ## Re: trouble understanding a part of the egg dropping puzzle

It is a good puzzle with a correct answer, but I admit that the explanation is a little obscure.

Let's go to his explanation of starting by dropping egg A from floor 10. If egg A breaks, we drop egg B from floor 1. If egg B does not break, we try floor 2, and so on. Thus, if we get to floor 9, we have had 10 drops, one using egg A and nine using egg B. Ten drops is our worst case if egg A breaks at floor 10. With me to here?

But what if egg A does not break when dropped from floor 10. Let's suppose we go up to floor 20 and drop egg A. If it breaks, we start on floor 11 and may have to go as high as floor 19. So our worst case is now eleven drops, two with egg A on floors 10 and 20 and potentially nine with egg B on floors 11 through 19. Each time we go up by ten floors the potential worst case grows by one. Now look what happens if we do the second drop of egg A from floor 19. If egg A breaks, then we have only eight floors to try with egg B, namely 11 through 18. So our worst case is still 10, two drops of egg A and potentially eight drops of egg B. To keep our worst case consistent, we have to reduce the number of potential uses of egg B by one for each extra drop of egg A.

Still with me?

But we chose our initial drop from floor 10 without any real rationale. So we would go 10, 19, 27, 34, 40, 45, 49, 52, 54, and still have 46 floors to go.

If we start at 14, we would go next to 27, 39, 50, 60, 69, 77, 84, 90, 95, 99, 100.