Jump to content
BrainDen.com - Brain Teasers
  • 0

Classic eggs problem


ujjagrawal
 Share

Question

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 by ujjagrawal
Link to comment
Share on other sites

6 answers to this question

Recommended Posts

  • 0

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.

Link to comment
Share on other sites

  • 0

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.

Link to comment
Share on other sites

  • 0

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.

Link to comment
Share on other sites

  • 0

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.

  • Upvote 1
Link to comment
Share on other sites

  • 0

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...
Link to comment
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Answer this question...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Loading...
 Share

  • Recently Browsing   0 members

    • No registered users viewing this page.
×
×
  • Create New...