Jump to content


Welcome to BrainDen.com - Brain Teasers Forum

Welcome to BrainDen.com - Brain Teasers Forum. Like most online communities you must register to post in our community, but don't worry this is a simple free process. To be a part of BrainDen Forums you may create a new account or sign in if you already have an account.
As a member you could start new topics, reply to others, subscribe to topics/forums to get automatic updates, get your own profile and make new friends.

Of course, you can also enjoy our collection of amazing optical illusions and cool math games.

If you like our site, you may support us by simply clicking Google "+1" or Facebook "Like" buttons at the top.
If you have a website, we would appreciate a little link to BrainDen.

Thanks and enjoy the Den :-)
Guest Message by DevFuse
 

Photo
* * * * * 1 votes

Classic eggs problem


  • Please log in to reply
6 replies to this topic

#1 ujjagrawal

ujjagrawal

    Junior Member

  • Members
  • PipPip
  • 67 posts
  • Gender:Male
  • Location:India

Posted 09 July 2012 - 11:47 AM

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, 09 July 2012 - 11:49 AM.

  • 0

#2 phil1882

phil1882

    Senior Member

  • Members
  • PipPipPipPip
  • 538 posts

Posted 09 July 2012 - 03:06 PM

Spoiler for 3 eggs

  • 0

#3 jim

jim

    Junior Member

  • Members
  • PipPip
  • 33 posts

Posted 09 July 2012 - 03:50 PM

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.
  • 0

#4 vinay.singh84

vinay.singh84

    Junior Member

  • Members
  • PipPip
  • 44 posts
  • Gender:Male
  • Location:King of Prussia

Posted 09 July 2012 - 06:49 PM

Spoiler for My guess

  • 0

#5 jim

jim

    Junior Member

  • Members
  • PipPip
  • 33 posts

Posted 09 July 2012 - 09:07 PM

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.
  • 1

#6 ujjagrawal

ujjagrawal

    Junior Member

  • Members
  • PipPip
  • 67 posts
  • Gender:Male
  • Location:India

Posted 10 July 2012 - 05:30 AM

Spoiler for Please use Spoilers
Good work dude... the same answer I have got but with different working...
  • 0

#7 ~andy~

~andy~

    Newbie

  • Members
  • Pip
  • 17 posts
  • Gender:Male
  • Location:UK

Posted 26 October 2012 - 03:04 PM

Spoiler for It's simple


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




0 user(s) are reading this topic

0 members, 0 guests, 0 anonymous users