You have two eggs and a building. Find the first floor from which the egg will break when the egg is dropped to the ground. What is the minimum number of steps you need to find the floor?

roundup(n/2) + 1 , where n is the first floor from which it actually breaks.Drop it from every alternate floor, starting from second floor .. and when it breaks, drop the second egg from the floor below.But this solution looks naive and silly .... is there a trick, here?

Are we supposed to take into account returning to the ground floor to retrieve the egg when it has not broken? What is a 'step' in this problem?

One can do a little bit better by taking M= [ N/3 ] (integer part) where N is the last floor (I am assuming european floor counting), try:(M+1) a) breaks, with the remaining egg go through 1,2,...,M (until it breaks) b) doesn't break try(2M+1) a) breaks, go through M+2,...,2M b) doesn't break go through 2M+2 to NAdjust slightly to add 1 to the middle interval if N is 2 mod 3 so we never try more than M+1 times.This strategy allows trying roughly 1/3 of the floors, more precisely [N/3] +1 at most.

QuoteOriginally posted by: zarnywhoopAre we supposed to take into account returning to the ground floor to retrieve the egg when it has not broken? What is a 'step' in this problem?ok.. I see the improvement you are (probably) trying to suggest: Drop the first egg from the second floor, then the second egg from the fourth floor ... and fetch the unbroken eggs together ... so on.

QuoteOriginally posted by: aymThis strategy allows trying roughly 1/3 of the floors, more precisely [N/3] +1 at most.Good .. but won't it be better doing this with N^0.5 .. rather than N/3 (where N is maximum number of floors) ?

Actually you can do better than this.Let M be the total maximum number of drops required for both eggs. If the first egg breaks on try 1, then egg may be dropped at most M-1 times. This requires that egg 1's first drop be from no higher than floor M.If egg 1 breaks on try 2, we may drop egg 2 at most M-2 times. Thus egg 1's second drop would be M-1 floors above the first drop, or floor M + (M-1).In general, if egg 1 breaks on try n then egg 2 is allowed at most M-n drops, and the corresponding nth floor number is:M + (M-1) + (M-2) + ... + (M-n+1)Note that n cannot exceed M, so the highest floor testable is :M + (M-1) + (M-2) + ... + (M-M+1)= (1 + 2 + ... + M)= M(M+1)/2So now we can find the smallest M such that M(M+1)/2 is greater than the number of floors

.

I am not sure what you mean. Let's say you try [ Sqrt(N) ] with the first egg and it breaks, greatbut if it doesn't, now you have to decide what startegy you want to use,It egg 1 doesn't break from N^0.5 floor ... drop it from 2*(N^0.5) .. and so on, till it breaks.The second egg will be needed to be dropped at most N^0.5 times.(and atmost egg 1 will be needed to be dropped N^0.5 times).So, max no. of drops = 2*(N^0.5)

Hi Bhutes,So lets say we have 105 floors then by your method we'll need about 20 drops, and if we go in steps of n/3 we will need about 35 drops whereas the method i was talking about achieves it in about 14 drops. Let me know if i've made a mistake.

wannabequantie, I have a simple question. Say the floor that breaks the egg is the last floor n.Then will you not try every floor until the last with the first egg? (and have M=n)I do not see a strategy of trials emerging from your count.

QuoteOriginally posted by: bhutesI am not sure what you mean. Let's say you try [ Sqrt(N) ] with the first egg and it breaks, greatbut if it doesn't, now you have to decide what startegy you want to use,It egg 1 doesn't break from N^0.5 floor ... drop it from 2*(N^0.5) .. and so on, till it breaks.The second egg will be needed to be dropped at most N^0.5 times.(and atmost egg 1 will be needed to be dropped N^0.5 times).So, max no. of drops = 2*(N^0.5)Yes, I see that it does work as well.Edit: I should have stayed with my first impression. Max is indeed 2 N^0.5 in this case.

Hi Aym,Let me work with an example, i probably didn't explain it properly. Lets say the number of floors is 105. Then you drop the first egg from floors 14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99, 102, 104, 105. So now if the egg were to break at 90 we know the egg hasn't broken at 84 so we drop the second egg from floors 85, 86, 87, 88, 89. So given any situation we need at most 14 drops to find out the floor from which the egg will break.

duplicate