Nov 10, 2009

2 eggs problem

* You are given 2 eggs.
* You have access to a 100-storey building.
* Eggs can be very hard or very fragile means it may break if dropped from the first floor or may not even break if dropped from 100 th floor.Both eggs are identical.
* You need to figure out the highest floor of a 100-storey building an egg can be dropped without breaking.
* Now the question is how many drops you need to make. You are allowed to break 2 eggs in the process

12 comments:

  1. 99, assuming at least one of the eggs survives that long.

    ReplyDelete
  2. Hey but its not optimum. Its possible to do it in lesser number of trials...

    ReplyDelete
  3. Well the answer is 14.

    Solution:

    *Suppose we drop the first egg from nth floor.

    *If it breaks start dropping the second egg from floor 1,2,3...n-1. If it doesn't break drop the first egg from (n)+(n-1)

    *If it breaks start dropping from n+1,n+2,n+3...n+n-2. If it doesn't break drop it from (n)+(n-1)+(n-2).

    And so on....

    So for a 100 building problem we should be able to cover the entire building using this approach.

    Therefore, 1+2+3........n = 100

    This yields the best value as 14. Since, sum of first 14 natural numbers is 105.


    Hence you need 14 trials and for that you drop eggs as per the strategy mentioned above.

    ReplyDelete
  4. you drop it from every 10th four, and when it breaks, you drop the second one, from the last 10th (if it breaks at 30, you drom from 21)
    the worst case senario is that it breaks at 100th folur, and in that case, you have made 19 drops.

    at:
    10, 20, 30, 40, 50, 60, 70, 80, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100

    the problem with the other one (Freddo) is that his sequence is the fuminachi sequence, and there are many numbers missing in that.
    his sequence is: 1-2-3-5-8-13... as you can seem 11 is missing, and so are many other numbers.

    ReplyDelete
  5. Yes, so in your solution you might require 19 drops. The solution i gave above requires only 14.

    To state it again, here it goes:

    drop according to this sequence - 14,27,39,50,60,69,77,84,90,95,99,100

    Please note that first difference of the above series yields 13,12,11,10 and so on. Only after 99 you will need to break the series as we are only given 100 floors.

    In this solution you would require 14 trials at a maximum.

    ReplyDelete
    Replies
    1. I think we need to average around the SQRT of 100 (i.e. higher segments sizes first) and then smaller later so that the av is 10.

      Delete
  6. havent u guys heard of binary search
    drop from 50th floor, if breaks drop from 25 else 75 ans so on.
    Like this requires LOG(2)100 steps

    ReplyDelete
  7. yes you are correct in saying that it's a binary search problem...


    But if u drop from the 50th floor and say if it breaks then you need 49 more steps....total: 50 steps...Dude, answer is 14

    ReplyDelete
  8. Tanishq GoyalOctober 08, 2010

    no u r wrong in saying that..it will require 50 steps in binary search..

    if the egg breaks frm 50th floor..u dont try from 49th floor next..u try from 25th floor..reducing the problem size by 2 in each step..the basic funda of binary search!!

    ReplyDelete
  9. Dude, will explain my solution later...let's talk about urs first..

    Suppose it breaks at 50.u then drop from 25th and suppose it breaks again...Games over!! coz both of ur eggs broke and you didn't still find the correct floor from where it starts breaking



    Answer is 14 and I'll give you the full solution...Why don't you try to get a smaller number and prove me wrong

    ReplyDelete
  10. Its a good answer, but this to me is a standard puzzle solving technique. However I won;t take away the answer from you, its most optimum.
    Personally, I'd rather boil the boil those eggs and then remove the shell and throw them from top...... :)
    Or even better just eat them forget the problem... Sorry I ate them eggs .. ha ha ha

    ReplyDelete