|
||||
Title: floors and eggs Post by crabweb on Aug 24th, 2005, 3:45am hi everyone , how's this puzzle There is a 100 storey building, you are provided with 2 eggs. There is a critical floor in the building where the egg will break when dropped. (suppose the egg breaks at floor n=20, then the egg will break on all floors n=20 to n=100 and they don't break from n=1 to n=19). Find the minimum no. of drops in the worst case so that you can identify the value of n. |
||||
Title: Re: floors and eggs Post by towr on Aug 24th, 2005, 5:14am Is there some sort of contest involving this puzzle or something? Because it's kind of suspicious to see it again so soon after the last time (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_medium;action=display;num=1124198189).. |
||||
Title: Re: floors and eggs Post by Grimbal on Aug 24th, 2005, 6:53am Anyway, since the subject comes up again, I have been thinking the optimal strategy is to drop one egg from the 1st floor and observe that it breaks. The version with marbles is more believable. |
||||
Title: Re: floors and eggs Post by rmsgrey on Aug 24th, 2005, 8:37am on 08/24/05 at 06:53:58, Grimbal wrote:
I feel like hijacking a thread today. Take the variant with cats instead. You have four cats and a 100 storey building. You are told that there is a range of floors that cats suffer serious injury when dropped from. Floors above and below that range merely stun the cats long enough to prevent them escaping before you can collect them for another drop. As soon as a cat suffers serious injury, it gets taken away by the RSPCA (or the local equivalent outside the UK). Once the fourth cat gets injured, your operation will be shut down by the authorities (so no getting additional cats) What is your optimal strategy for identifying theuper and lower limits of the injury region? Apparently, statistical research into existing reported falling cats shows that the extent of typical injuries reaches a maximum around the 7th floor and declines to a roughly constant level at higher floors. For puzzle purposes, assume that the desired range could be any interval in [1,100] - including the situation where every drop produces serious injuries. |
||||
Title: Re: floors and eggs Post by cat_hater on Aug 24th, 2005, 8:50am You should setup a funnel outside the building that will catch the cats and funnel them into a wood chipper (gas powered). By doing this you completely elliminate the need to study injuries and are guaranteed to be shut down by authoritiies. |
||||
Title: Re: floors and eggs Post by Sjoerd Job Postmus on Aug 24th, 2005, 10:15am Ay! So, it could even be that only floor 42 causes injury? Good luck for finding that optimaly! That's like number guessing without the "Higher"/"Lower"!!!!! |
||||
Title: Re: floors and eggs Post by SMQ on Aug 24th, 2005, 12:20pm Well, worst-case performance will be 99 drops--there may be only one floor which breaks the cat. I would think something like the following would have good avearge performance: - drop cat 1 from floors 1, 9, 17, ..., 97, 5, 13, ..., 93, 3, 7, 11, ..., 99, 2, 4, 6, 8, ..., 100 until it breaks. Call this floor A. - drop cat 2 from the floor just above (the highest floor below floor A which was tested with cat 1) incrementally up by one floor until it breaks; this establishes the lower bound. - repeat inverted with cats 3 and 4 to establish the upper bound. (though you never need test below floor A+1) --SMQ |
||||
Title: Re: floors and eggs Post by JocK on Aug 24th, 2005, 2:22pm on 08/24/05 at 08:37:03, rmsgrey wrote:
I interpret 'optimal' as minimising the averge number of cat drops whilst ensuring finding the exact range by 'consuming' no more than four cats. My strategy would be based on establishing: 1) a lowest floor (L1) that is known to cause injury 2) a highest floor (H1) that is known to cause injury 3) a highest floor (L0) smaller than L1 that is known not to cause injury 4) a lowest floor (H0) higher than H1 that is known not to cause injury At start you have the initial values L0 = 0 and H0 =101, whilst L1 and H1 are unknown. So we use the first cat to establish initial values for these two parameters using an interval halving method: Drop the cat from floors 50; 25, 75; 12, 37, 63, 88; 6, 18 .. until it is taken away by the RSPCA. The last floor from which the cat was dropped establishes the initial value for L1 and H1. Obviously, unless the cat was taken away immediately following the first drop, we also have updated values for L0 and/or H0 being the highest floor tested that is smaller than L1, and the lowest floor tested that is higher than H1, respectively. Having established values that satisfy L0 < L1 =< H1 < H0, we use the second cat to sharpen these values using - again - interval halving methods: A) establish which of the two uncertainty ranges L1 - L0 or H0 - H1 is bigger. B) drop cat two from the level closest to the midpoint of the biggest uncertainty range B) If the cat is still healthy: update L0 (or H0) with the last floorlevel, and repeat step A) C) If the cat is wounded, update L1 (or H1) with the last floorlevel. With the updated ranges L0 < L1 =< H1 < H0, we proceed with cats three and four to ensure we arrive at L1= L0 +1 and H1 = H0 - 1: Drop cat three from level L0 + 1 and increase by one floor until it gets hurt, and: drop cat four from level H0 - 1 and decrease by one floor until it gets hurt. Not being given the probability distribution of the value of H1 - L1, there is little I can say about the average number of drops required. |
||||
Title: Re: floors and eggs Post by m_prithvin13 on Sep 6th, 2005, 3:24am [hide] Throw the first egg from level 14, and (as long as it doesn't break) increase the floorlevel one less than the last increase. i.e 14, 27, 39, 50, 50, 69, 77, 84, 90, 95, 99 And then use the second egg to work up from the last floor that the egg didn't break till you reach the floor that the egg breaks and that is your answer. Minimum number of drops needed is 14 [/hide] |
||||
Title: Re: floors and eggs Post by JocK on Sep 6th, 2005, 4:45am on 08/16/05 at 11:07:00, JocK wrote:
on 09/06/05 at 03:24:53, m_prithvin13 wrote:
Next time you copy & paste, please correct the typo... (50, 60) ::) |
||||
Title: Re: floors and eggs Post by towr on Sep 6th, 2005, 5:43am lol ;D |
||||
Title: Re: floors and eggs Post by auch on Sep 8th, 2005, 12:50pm What a shame m_prithvin. You shud have atleast given the reference from where u got the solution. |
||||
Title: Re: floors and eggs Post by Swapnil Dipankar on Oct 13th, 2005, 7:07pm Interesting article on the same problem... http://ite.pubs.informs.org/Vol4No1/Sniedovich/ -Swapnil Dipankar. |
||||
Powered by YaBB 1 Gold - SP 1.4! Forum software copyright © 2000-2004 Yet another Bulletin Board |