Results 1 to 3 of 3
Like Tree1Thanks
  • 1 Post By Tuufless

Thread: trouble understanding a part of the egg dropping puzzle

  1. #1
    Newbie
    Joined
    Jul 2013
    From
    mathworld
    Posts
    3

    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

    Please advise.
    Thanks.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    Nov 2009
    Posts
    151
    Thanks
    64

    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.
    Thanks from JeffM
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Feb 2014
    From
    United States
    Posts
    1,650
    Thanks
    779

    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Trouble understanding
    Posted in the Advanced Statistics Forum
    Replies: 1
    Last Post: Jul 25th 2014, 08:19 AM
  2. trouble understanding this problem
    Posted in the Calculus Forum
    Replies: 5
    Last Post: Mar 16th 2014, 07:09 PM
  3. [SOLVED] Trouble understanding Subspaces
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: Sep 30th 2010, 12:37 AM
  4. Replies: 3
    Last Post: Apr 11th 2009, 05:06 PM
  5. Having trouble understanding this example
    Posted in the Trigonometry Forum
    Replies: 5
    Last Post: Mar 21st 2009, 12:33 AM

Search Tags


/mathhelpforum @mathhelpforum