wu :: forums (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
riddles >> medium >> floors and eggs
(Message started by: crabweb on Aug 24th, 2005, 3:45am)

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:
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.

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:
What is your optimal strategy for identifying theuper and lower limits of the injury region?.


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:
throw the first marble from level 14, and - as long as it continuous to survive - increase the floorlevel one less than the last increase:

14, 27, 39, 50, 50, 69, 77, 84, 90, 95, 99

and then use the second marble to work up one floor at a time from the one but last floor tested (i.e. the last floor for which the first marble survived).

Maximum number of drops needed: 14



on 09/06/05 at 03:24:53, m_prithvin13 wrote:
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


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