Classic eggs problem

[ujjagrawal]

You have been given three eggs and your job is to figure out how high an egg can fall from a 120 story building before it breaks. The eggs might break from the first floor, or might even survive a drop from the 120th floor, you have no prior information about it. Except all three eggs are know to be of exactly same strength.

What's the most efficient way to drop the eggs i.e. reducing the number of times you need to drop eggs and still able to determine the answer? You are allowed to break all three eggs, as long as you identify the correct floor afterwards.

After you've solved the above problem, generalize. Define the "break floor" as the lowest floor in a building from which an egg would break if dropped. given an n story building and a supply of m eggs, find the strategy which minimizes (in the worst case) the number of experimental drops required to determine the break floor.

Edited July 9, 2012 by ujjagrawal

[phil1882]

so it seems to me the goal is not so much to minimize the number of drops, but to maximize the floor distance.

with 1 egg, you can only have a distance of 1. (must start dropping from the first floor, and go up 1 floor at a time.)

with 2 eggs, you can have a distance of 4. (may start on the 4th floor and increase by 4.)

with 3 eggs, you can have a distance of 13. (may start on the 13th floor, and increase by 13.)

with 4 eggs, you cna have a distance of 40. and so on.

[jim]

Reverse the problem and let m be the number of drops, and then n is the tallest building that can be done using this number of drops. If you only have one egg n=m. With two eggs n = 1 + 2 +...+m = m(m+1)/2---call this b(m). With three eggs we get n = b(1) + ...+b(n) which we can call c(n) and so on. Now c(m) is half the sum of 1+...+m and 1+...+m^2 or half m(m+1)/2 and m(m+1)(2m+1)/6 so we get c(m) =(1/6)m^3 + (1/2)m^2 + (1/3)m or c(m) = (m^3 + 3m^2 +2m) / 6. For three eggs we get c(8) = 120 so the answer to the basic problem is 8.

[vinay.singh84]

max # of drops = ceil( n/(2^(m-1)) ) + (m - 1) This is because m eqgs allow you a span of 2^(m-1) eqgs to find the correct floor (1 egg to get the span and the rest to get the precise floor). If the number larger than 2^(m-1), you'll have to drop at half a span higher than each multiple of 2^(m - 1) (+ 2^(m - 1) until you reach the span. In this scenario 3 eggs, you're span is 2^2=4; ceil (120/4 ) + 2 = 30 + 2 = 32 (You drop at 2,6,10 and so forth until you hit your span (of 4), then use the remaining two eggs to figure out the floor.

[jim]

Correction. Let h(k,m) be the height that can be handled with k eggs and up to m drops. Above I used a recursion of h(k,n) = h(k,n-1) + h(k-1,m) when I should have used a slightly different formula. Let the base at any time be the highest known safe floor. With k eggs and m drops left we can afford to skip h(k-1,m-1) floors and do our next drop at base + h(k-1,m-1) + 1. When an egg breaks the base remains the same and both k and m decrease by 1. If the egg doesn't break, increase the base by h(k-1,m-1) + 1 and then decrease just m by 1.

h(1,m) = m where start dropping at the lowest floor and work upwards one at a time.

h(2,m) = (m-1)+1 + (m-2)+1 + ... + (m-m)+1 = SUM of m, m-1, m-2, ...1 = m(m+1) / 2

h(3,m) = (m-1)m/2 +1 + (m-2)(m-1)/2+1 + ... = SUM (1/2)j^2 - (1/2)j +1 for j from 1 to m and we get

(1/12)m(m+1)(2m+1) - (1/4)m(m+1) + m = (1/6)(m^3 -m) + m = (1/6)(m-1)m(m+1) + m. so 8 is not enough bu 9 drops would let us go as high as 120 + 9 which is enough.

[ujjagrawal]

Correction. Let h(k,m) be the height that can be handled with k eggs and up to m drops. Above I used a recursion of h(k,n) = h(k,n-1) + h(k-1,m) when I should have used a slightly different formula. Let the base at any time be the highest known safe floor. With k eggs and m drops left we can afford to skip h(k-1,m-1) floors and do our next drop at base + h(k-1,m-1) + 1. When an egg breaks the base remains the same and both k and m decrease by 1. If the egg doesn't break, increase the base by h(k-1,m-1) + 1 and then decrease just m by 1.

h(1,m) = m where start dropping at the lowest floor and work upwards one at a time.

h(2,m) = (m-1)+1 + (m-2)+1 + ... + (m-m)+1 = SUM of m, m-1, m-2, ...1 = m(m+1) / 2

h(3,m) = (m-1)m/2 +1 + (m-2)(m-1)/2+1 + ... = SUM (1/2)j^2 - (1/2)j +1 for j from 1 to m and we get

(1/12)m(m+1)(2m+1) - (1/4)m(m+1) + m = (1/6)(m^3 -m) + m = (1/6)(m-1)m(m+1) + m. so 8 is not enough bu 9 drops would let us go as high as 120 + 9 which is enough.

Good work dude... the same answer I have got but with different working...

[~andy~]

An egg can fall from the 120th floor, or even the roof, it will not break till it hits the ground

Can't believe you guys didn't get that one!