Author |
Topic: floors and eggs (Read 2404 times) |
|
crabweb
Newbie
Posts: 6
|
 |
floors and eggs
« on: Aug 24th, 2005, 3:45am » |
 Quote  Modify
|
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.
|
|
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender: 
Posts: 13730
|
|
Re: floors and eggs
« Reply #1 on: Aug 24th, 2005, 5:14am » |
Quote Modify
|
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..
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: floors and eggs
« Reply #2 on: Aug 24th, 2005, 6:53am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
    
Gender:
Posts: 2873
|
|
Re: floors and eggs
« Reply #3 on: Aug 24th, 2005, 8:37am » |
Quote Modify
|
on Aug 24th, 2005, 6:53am, 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.
|
|
IP Logged |
|
|
|
cat_hater
Guest
|
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.
|
|
IP Logged |
|
|
|
Sjoerd Job Postmus
Full Member
Posts: 228
|
|
Re: floors and eggs
« Reply #5 on: Aug 24th, 2005, 10:15am » |
Quote Modify
|
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"!!!!!
|
|
IP Logged |
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: floors and eggs
« Reply #6 on: Aug 24th, 2005, 12:20pm » |
Quote Modify
|
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
|
|
IP Logged |
--SMQ
|
|
|
JocK
Uberpuzzler
Gender:
Posts: 877
|
|
Re: floors and eggs
« Reply #7 on: Aug 24th, 2005, 2:22pm » |
Quote Modify
|
on Aug 24th, 2005, 8:37am, 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.
|
| « Last Edit: Aug 24th, 2005, 2:51pm by JocK » |
IP Logged |
solving abstract problems is like sex: it may occasionally have some practical use, but that is not why we do it.
xy - y = x5 - y4 - y3 = 20; x>0, y>0.
|
|
|
m_prithvin13
Newbie
Gender:
Posts: 17
|
|
Re: floors and eggs
« Reply #8 on: Sep 6th, 2005, 3:24am » |
Quote Modify
|
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
|
|
IP Logged |
|
|
|
JocK
Uberpuzzler
Gender:
Posts: 877
|
|
Re: floors and eggs
« Reply #9 on: Sep 6th, 2005, 4:45am » |
Quote Modify
|
on Aug 16th, 2005, 11:07am, 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 Sep 6th, 2005, 3:24am, 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) 
|
|
IP Logged |
solving abstract problems is like sex: it may occasionally have some practical use, but that is not why we do it.
xy - y = x5 - y4 - y3 = 20; x>0, y>0.
|
|
|
auch
Guest
|
What a shame m_prithvin.
You shud have atleast given the reference from where u got the solution.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print
Remove