Author |
Topic: HARD: egg dropping (Read 12688 times) |
|
Frank gevaerts
Guest
|
Egg Dropping
I can get to 19 :
- drop the first egg from the 10th, 20th,..100th floor
- As soon as it breaks, start from the first floor above the last successfull drop, and go up one floor a time.
Worst case : 99th floor: the first egg breaks at the 10th drop, and the second egg has to be dropped 9 times (91 to 99)
// Link added by moderator //
|
| « Last Edit: Aug 28th, 2003, 6:11pm by Icarus » |
 IP Logged |
|
|
|
Jon
Guest
|
Try goin in halfs:-
Say floor 2 is the max.
Drop from floor 50,
then 25
then 12
then 6
then 3
then 2
Or if its 35 (say)
Drop from 50
then 25
then 37 (25 + 12)
then 31 (25 +6)
then 34 (31 + 3)
then 36 (34 + 2)
then 35.
I _think_ its whats called a B tree seach algorithm. But not 100%.
|
|
IP Logged |
|
|
|
drdedos
Guest
|
I was thinking more along the lines of Frank's answer. Jon is wrong. In his first example, he would have broken both eggs and would only know that it was less than 25. He would not have any eggs left to test the lower floors. Every 10 is the most efficient because it is the square root of 100. If you did every 20, say, it could take up to 4+19 tries. If you did every 5, it could take up to 19+4 tries. 10 is most efficient.
|
|
IP Logged |
|
|
|
Green Eggs and Ham
Guest
|
A better solution is found by assuming that you want all intervals to require the same number of trials. The solution above requires 10 searches for the first interval, then 11, then 12, and so forth.
Specifically, assume that you start at some index N. If the egg breaks, you then have to walk (N-1) steps with the other egg to find the correct floor. If on the first drop, the egg didn't break, you then make you next interval (N-1) floors long. If the first egg breaks on the 2nd drop, the 2nd egg must be tested on (N-2) floors. Both of these intervals will require N trials to search.
The next interval will be (N-2) steps away, etc. So you need to find the sum of (N + (N-1) + (N-2) ... + 1) >= 100. Which is the same as N(N+1)/2 >= 100. N^2 + N >= 200. So N should be 14.
|
|
IP Logged |
|
|
|
yermo
Guest
|
this is a trick question. The egg can fall 100 stories before it breaks. Just drop it from the top of the building. The riddle never said that the egg had to survive the fall.
|
|
IP Logged |
|
|
|
deusued
Newbie
Posts: 1
|
 |
Re: HARD: egg dropping
« Reply #5 on: Jul 25th, 2002, 10:25pm » |
 Quote  Modify
|
It's been a while since I took Computer Networks (7 years), but if I recall, the hint to this problem refers to the algorithm by which TCP/IP interfaces adhere to to resolve collisions.
Interfaces (again, this is fuzzy) "back-off" on collisions a wait a period of 2^n time units before sending again, where n is the number of previous collisions.
So.. relating this concept to this problem (Egg Dropping), I'm thinking something related to LN(N).
My rough answer, though, is.. start at floor 9, testing every 8th floor thereafter (9,17,25,33) until a break [note, after floor 97, try floor 100]. Starting from the last successful floor, try each incremental floor.
First Egg Floors: 9,17,25,33,41,49,57,65,73,81,89,97,100
Floor Second Egg Floors # Tries
99 98,99 15 tries
45 42,43,44,45,46 11 tries
9 10 3 tries
I doubt this solution is optimal, but it's not the worst case.
|
|
IP Logged |
|
|
|
Viorel Canja
Guest
|
An optimal solution can be found using dynamic programming.
let v[k] be the minimal number of egg drops needed to find the solution for a k story building
1. v[0]=0
2. assuming v[i] is computed for all i , 0 <= i < k
v[k] = min ( max ( j-1 , v[k-j] ) ) + 1
For a 100 story building 14 egg drops is minimum
|
|
IP Logged |
|
|
|
Viorel Canja
Guest
|
I forgot to mention that 1 <= j <= k 
|
|
IP Logged |
|
|
|
william wu
wu::riddles Administrator
Gender: 
Posts: 1291
|
 |
Re: HARD: egg dropping
« Reply #8 on: Jul 26th, 2002, 4:58am » |
Quote Modify
|
Hi guys. Nice discussions! Well, here's a copy of a lecture given last year by Dr. Satish Rao, my CS170 (algorithms) professor. It starts off with the eggs riddle, and then describes how this riddle applies to network loading.
http://www.ocf.berkeley.edu/~wwu/riddles/eggs.ps
As an exercise, you can try proving that there does not exist a more efficient algorithm using just 2 eggs.
|
|
IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
Kozo Morimoto
Guest
|
Yeah 14 times seems like a good solution, with decreasing storeys after each successful drop.
The sequence goes like:
14,27,39,50,60,69,77,84,90,95,99,100
So if egg breaks after the first drop, you have max of 13 more (1 to 13) for a total of 14 drops
If the first egg breaks on the 2nd drop, you have max of 12 more (15 to 26) for a total of 14 drops etc etc
|
|
IP Logged |
|
|
|
william wu
wu::riddles Administrator
Gender:
Posts: 1291
|
 |
Re: HARD: egg dropping
« Reply #10 on: Jul 30th, 2002, 6:27pm » |
Quote Modify
|
I've added a note to the riddle now ... generalize the problem and find the optimal algorithm for a building of N floors, given D eggs to play with. Have fun.
|
|
IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
Viorel Canja
Guest
|
The dynamic programming solution is very easy to generalize. One problem with this solution is that it has O(N^2*D) time complexity and O(N*D) space complexity. I think this solution can be optimized and finally reduced to a formula.
|
|
IP Logged |
|
|
|
sharad kedia
Guest
|
for genral one .. it sud be (n+D-1)C(D) >= N
where
D is no. of eggs
N story building
n no. of drops
|
|
IP Logged |
|
|
|
snaily
Newbie
Posts: 5
|
|
Re: HARD: egg dropping
« Reply #13 on: Feb 19th, 2004, 11:49am » |
Quote Modify
|
This topic has been dead for 7 months, but I can't help myself. In case anyone else reads this thread I just want to point out that testing the 100th floor (as all the above people mentioned) is proof that math really is the opposite of thought. If the egg doesn't break on the 99th floor, then you know 100 is the answer. You don't have to prove what is obvious. Simply test 14, 27, 39, 50, 60, 69, 77, 84, 90, 95, then if the egg doesn't break test 96, 97, 98 and 99, for a total of 14. If you test 100 (like in all the above posts) then if the number is 99 you'd need 15 attempts and would be wrong. So the answer is only true if you "don't" test the 100th floor, since if that is the answer it will be obvious anyway.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: HARD: egg dropping
« Reply #14 on: Feb 19th, 2004, 1:10pm » |
Quote Modify
|
If you don't test the 100th floor, you won't know if the egg will break from that height or not. So you won't have answered the question if you don't test it..
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
John_Gaughan
Uberpuzzler
Behold, the power of cheese!
    
Gender:
Posts: 767
|
|
Re: HARD: egg dropping
« Reply #15 on: Feb 19th, 2004, 1:28pm » |
Quote Modify
|
After reading the thread I assumed it had to break, but the problem specifically states it may survive all 100 stories.
:: With only two eggs, the worst case scenario is 51 drops. Drop at 2, 4, 6, 8, ..., 100. If it breaks, drop the second egg at the next lower floor.
For example, if the first egg survives 58 but breaks at 60, drop the second at 59. If it breaks, then 59 is the floor. If it survives, then 60 is the floor.
There may be a more optimal solution, but the problem asked for the worst-case scenario. ::
|
|
IP Logged |
x = (0x2B | ~0x2B)
x == the_question
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: HARD: egg dropping
« Reply #16 on: Feb 19th, 2004, 1:43pm » |
Quote Modify
|
and asks for the worst case of the best algorithm, not the worst algorithm 
Just one step better would be to use the first egg and go 10,20,30,40,50,60,70,80,90,100
then if it breaks at say 100, start with the second egg, 91,92,93,94,95,96,97,98,99 Worst case: 19
And you can still do better (as is shown earlier in the thread)
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
rmsgrey
Uberpuzzler
 
Gender:
Posts: 2873
|
|
Re: HARD: egg dropping
« Reply #17 on: Feb 20th, 2004, 2:31pm » |
Quote Modify
|
You can get a worse successful algorithm (still not dropping more than once from a given floor) by dropping from each floor in turn from the ground up (if you insist on making use of both eggs, then drop one from the top to start)
If you don't restrict the number of times you drop from a given floor, then you can get arbitrarily bad performance out of algorithms that guarantee success except when the egg breaks from the first floor (when you can't make more than one drop per egg).
|
|
IP Logged |
|
|
|
Brad711
Newbie
Gender:
Posts: 10
|
|
Re: HARD: egg dropping
« Reply #18 on: Dec 11th, 2004, 9:26am » |
Quote Modify
|
Ok, I tried this, AND IT DROPPED ON THE FIRST STORY! Man, just drop it from the first story and when it breaks, you have your answer.
|
|
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2873
|
|
Re: HARD: egg dropping
« Reply #19 on: Dec 12th, 2004, 11:24am » |
Quote Modify
|
on Dec 11th, 2004, 9:26am, Brad711 wrote:| Ok, I tried this, AND IT DROPPED ON THE FIRST STORY! Man, just drop it from the first story and when it breaks, you have your answer. |
|
And if you're dropping them into a swimming pool, or into thick bushes?
Or you hard boil them first?
|
|
IP Logged |
|
|
|
Erez
Guest
|
to make it a bit more complicated:
find an algorithm that calculates
E(n,k).
Where E is the maximum number of throws until the egg breaks.
let K be the number of eggs.
let n be a n story building.
|
|
IP Logged |
|
|
|
Ganon
Guest
|
Actually I think the egg will reach a terminal velocity in far fewer than 100 floors. If the (very strong and presumably hard boiled) egg was to break at a higher floor than the one from which it could reach terminal velocity, it would be due primarily due to the stresses incurred from previous drops and wouldn't be a valid test on the strength of the two original (and presumably identical) eggs. Sounds good for networking though.. 
|
|
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2873
|
|
Re: HARD: egg dropping
« Reply #22 on: Feb 22nd, 2005, 5:37am » |
Quote Modify
|
on Feb 21st, 2005, 4:48pm, Ganon wrote:Actually I think the egg will reach a terminal velocity in far fewer than 100 floors. If the (very strong and presumably hard boiled) egg was to break at a higher floor than the one from which it could reach terminal velocity, it would be due primarily due to the stresses incurred from previous drops and wouldn't be a valid test on the strength of the two original (and presumably identical) eggs. Sounds good for networking though..
|
|
If you say it's 4 meters per storey, assume gravity to be 10m/s/s, and neglect air resistance, then 100 storeys would be 400m, take about 9 seconds to fall, and reach a speed of 90 m/s (or about 25% of the speed of sound). Eggs have a pretty aerodynamic shape, so, while I wouldn't expect them to reach that speed, I wouldn't be surprised to find them still accelerating after 100 storeys. Does anyone actually have any data?
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: HARD: egg dropping
« Reply #23 on: Feb 22nd, 2005, 6:15am » |
Quote Modify
|
If you really want to drop eggs from a building, check this.
http://www.geocities.com/r_dman2000/egg_drop_project.htm
Else, the terminal velocity is proportional to the square root of the mass divided by the area. For a man, the terminal velocity is some 56 m/s. If a man is 80 kg and 0.72 square meters (a rough estimate, in a horizontal position) and an egg is 50 g and 20 square centimeters, that would put the terminal velocity of an egg at 26 m/s.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print
Remove
