Author |
Topic: Egg Dropping (Read 33343 times) |
|
continuum
Newbie
 
Gender: 
Posts: 14
|
 |
Re: Egg Drop: any solutions better than this?
« Reply #25 on: Sep 19th, 2002, 4:44pm » |
 Quote  Modify
|
Chronos, what wanted to say was:
1) Minimize the number of drops needed, subject to a number of floors and eggs.
2) Maximize the number of floors covered, subject to a number of drops and eggs.
The problems (1) and (2) are dual problems.
But I agree with you that formally what I said is not that. 
|
|
 IP Logged |
|
|
|
BNC
Uberpuzzler
Gender:
Posts: 1732
|
|
Re: Egg Drop: any solutions better than this?
« Reply #26 on: Dec 26th, 2002, 12:23am » |
Quote Modify
|
Late to join....
The answers posted here are similar to the one I got (although I used brute-force for the idea).
But, here is an "outside the box" idea  :
1. Incubate both eggs until hatched
2. Pray that you'll get 1 male + 1 female (changes better for larger number of eggs).
3. Breed the chicken, wait for them to lay eggs.
4. Now you have as many eggs as you want. Use binary split (the "lion in the desert" method), and get the answer in LogN attempts.
|
|
IP Logged |
How about supercalifragilisticexpialidociouspuzzler [Towr, 2007]
|
|
|
jollytall
Senior Riddler
Gender:
Posts: 585
|
|
Re: Egg Dropping
« Reply #27 on: Oct 29th, 2012, 12:35am » |
Quote Modify
|
It has just been warmed up again in the Easy section, but I rather reply to the most complete thread, i.e. this.
Actually eggs/marbles do not get tired, so it is not a really practical question how to minimise the number of drops. It is much more relevant to answer how many floors you have to climb to figure out the max floor (no elevator, sorry)?
If I am not mistaken, there are two separate questions/solutions:
- What is the minimum number of floors you have to climb with the optimal strategy, in the worst case scenario?
- What is the minimum expected value of floors you have to climb with the optimal strategy?
The "optimal strategy" in the two questions might be different.
|
| « Last Edit: Oct 29th, 2012, 12:45am by jollytall » |
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
   
Gender:
Posts: 2873
|
|
Re: Egg Dropping
« Reply #28 on: Oct 29th, 2012, 7:01am » |
Quote Modify
|
on Oct 29th, 2012, 12:35am, jollytall wrote:It has just been warmed up again in the Easy section, but I rather reply to the most complete thread, i.e. this.
Actually eggs/marbles do not get tired, so it is not a really practical question how to minimise the number of drops. It is much more relevant to answer how many floors you have to climb to figure out the max floor (no elevator, sorry)?
If I am not mistaken, there are two separate questions/solutions:
- What is the minimum number of floors you have to climb with the optimal strategy, in the worst case scenario?
- What is the minimum expected value of floors you have to climb with the optimal strategy?
The "optimal strategy" in the two questions might be different. |
|
Do you have to descend to tell whether the egg splattered?
|
|
IP Logged |
|
|
|
jollytall
Senior Riddler
Gender:
Posts: 585
|
|
Re: Egg Dropping
« Reply #29 on: Oct 29th, 2012, 9:11am » |
Quote Modify
|
No, you can see it. So, you can climb on with the second one, if the first was OK, or climb down only as much as you need to, if it splashed.
|
|
IP Logged |
|
|
|
jollytall
Senior Riddler
Gender:
Posts: 585
|
|
Re: Egg Dropping
« Reply #30 on: Nov 11th, 2012, 11:09am » |
Quote Modify
|
It seems more complicated than I thought. I could not find an easy logic to optimise the number of climbs. Brute force has its problems, simply because there are 2^99 strategies.
Even if we want to optimise the number of climbs, the logic of the strategy is the same. As long as we have two balls, we can go ahead with relatively large steps, but as soon as we have only one ball, we have to go floor by floor from the last tested safe floor+1 upto the the floor right below the one where the first ball broke (when the highest safe floor is that one).
While for the original riddle (optimise the maximum number of drops for the worst case scenario) the solution is simple for FLOORS=15 (stop at 5, 9, 12, 14, 15) it took me some brute force to get it for the optimisation of the number of climbs. I counted every climb twice (up and down, including at the end a last descend). I calculated the optimal strategy both for the Worst case as well as the Average. (btw. what is the best strategy to optimise the Average/Expected number for drops?)
The solution is to stop at 9, 12, 14, 15 for the Worst Case giving 82 climbs if the safe floor is the the 14th or 15th. Strange that it is the same as for the drops, except that we skip the fist stop at 5.
For the average the optimal solution is 8, 13, 15 with an Average Climb of 40.75.
I also made FLOORS=21.
The original is 6, 11, 15, 18, 20, 21
The Worst case for climbs is 10, 15, 18, 20, 21 with 148 climbs, still very similar to the original.
The Average case is 10, 14, 17, 21, with 72.09 climbs.
For higher number of floors it might need an iterative algorithm to guess the best.
|
|
IP Logged |
|
|
|
antkor
Newbie
Posts: 30
|
|
Re: Egg Dropping
« Reply #31 on: Jan 3rd, 2014, 5:44pm » |
Quote Modify
|
recently i came across a more difficult variant where you need to find the minimum average value of drops required to find the lowest floor which the egg breaks, or the highest floor the egg does not break. Thought to give the variant if anyone is interested.
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Egg Dropping
« Reply #32 on: Jan 3rd, 2014, 11:10pm » |
Quote Modify
|
Is it still with the restriction that you only have two eggs to break?
|
|
IP Logged |
|
|
|
antkor
Newbie
Posts: 30
|
|
Re: Egg Dropping
« Reply #33 on: Jan 4th, 2014, 6:47am » |
Quote Modify
|
on Jan 3rd, 2014, 11:10pm, Grimbal wrote:| Is it still with the restriction that you only have two eggs to break? |
|
yes. and the eggs have the same resistance if they don't break etc. I will give a hint in case it is needed. The floor selection applied is still 14,27,39 etc but if you continue the same strategy as the classical problem you will end up with an average of 10.35 (if i remember correctly) which is not optimal. So, near the top, the floor selection has to be altered a bit, in order to achieve the optimal average value. This means that the latest selections 84, 90, 95, 99, 100 have to be altered, but i won't tell how, so that you can think about it!
|
|
IP Logged |
|
|
|
rloginunix
Uberpuzzler
Posts: 1029
|
|
Re: Egg Dropping
« Reply #34 on: Jan 4th, 2014, 10:31am » |
Quote Modify
|
Guys, for the last three weeks or so I've been pondering the optimal 2-egg 100 floors solution. I think that what's antkor is asking.
I'm a bit raw but do you guys mind if I post my line of reasoning. I also think I have a proof.
It's lot's of text though.
My tentative answer is 14.
And if you find my proof rigorous enough then it's not the average it's the optimal solution.
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Egg Dropping
« Reply #35 on: Jan 4th, 2014, 4:29pm » |
Quote Modify
|
The meaning of "optimal" depends what you optimize.
In the original problem, the question was to optimize the worst case, the maximum number of drops. In the last variation, the question is to optimize the average number of drops.
|
|
IP Logged |
|
|
|
rloginunix
Uberpuzzler
Posts: 1029
|
|
Re: Egg Dropping
« Reply #36 on: Jan 4th, 2014, 6:44pm » |
Quote Modify
|
I see. Then I've solved the original problem with a proof - optimal number of drops in the worst case.
The definition of the average number of drops then is an arithmetic average between the worst and best cases?
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Egg Dropping
« Reply #37 on: Jan 5th, 2014, 2:30am » |
Quote Modify
|
No. I would say it is the average between the 101 possible answers.
|
|
IP Logged |
|
|
|
rloginunix
Uberpuzzler
Posts: 1029
|
|
Re: Egg Dropping
« Reply #38 on: Jan 5th, 2014, 11:04am » |
Quote Modify
|
Got it.
Thanks, Grimbal.
|
|
IP Logged |
|
|
|
rloginunix
Uberpuzzler
Posts: 1029
|
|
Re: Egg Dropping
« Reply #39 on: Jan 5th, 2014, 12:01pm » |
Quote Modify
|
I think I'm on to something. Check out this pattern.
A sample 10-story building analysis. From solving the worst case scenario optimization problem we already know that 4 tests is the answer - the testing floors are 4, 7, 9 and 10. Let's build a table for the average number of drops. The first column is the floor number, the second column is the number of drops and the third helper column are the floors we do the drops from if the floor in the first column is bad:
01-st: 2 (4, 1)
02-nd: 3 (4, 1, 2)
03-rd: 4 (4, 1, 2, 3)
04-th: 4 (4, 1, 2, 3)
05-th: 3 (4, 7, 5)
06-th: 4 (4, 7, 5, 6)
07-th: 4 (4, 7, 5, 6)
08-th: 4 (4, 7, 9, 8 )
09-th: 4 (4, 7, 9, 8 )
10-th: 4 (4, 7, 9, 10)
We see that the average number of drops for the 10-story building is 37/10 = 3.7.
We also see that the totals max out at the top floors while being the smallest at the lower floors. This is similar to my worst case scenarios research and this is where the optimization opportunity likely is.
I will now run a sample analysis for a 100-story building.
|
|
IP Logged |
|
|
|
rloginunix
Uberpuzzler
Posts: 1029
|
|
Re: Egg Dropping
« Reply #40 on: Jan 5th, 2014, 12:57pm » |
Quote Modify
|
I've built 12 tables covering all 100 floors based on the worst case scenario testing scheme. The sum total of all the drops ran thus:
1*12 + 11*2*14 + 11*13 + 11*12 + 10 *11 + 9*10 + 8*9 + 7*8 + 6*7 + 5*6 + 4*5 + 3*4 + 2*3 + 1*2 = 1035
1035/100 = 10.35
But apparently that is not the lowest average possible.
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Egg Dropping
« Reply #41 on: Jan 6th, 2014, 5:51am » |
Quote Modify
|
I get
1045/101 = 10.3465
|
|
IP Logged |
|
|
|
rloginunix
Uberpuzzler
Posts: 1029
|
|
Re: Egg Dropping
« Reply #42 on: Jan 6th, 2014, 10:50am » |
Quote Modify
|
My testing floors were 14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99 and 100.
The first column defines a bracket - a range of floors and the second column is the number of drops it takes to tell with certainty that the current floor in the current bracket really hates eggs. Since the number of drops from one floor to another within the bracket only differs by one I only give the number of drops for the initial floor and the number of drops for the last floor in the current bracket - a range in other words:
001 - 014 ..... 02 - 14
015 - 027 ..... 03 - 14
028 - 039 ..... 04 - 14
040 - 050 ..... 05 - 14
051 - 060 ..... 06 - 14
061 - 069 ..... 07 - 14
070 - 077 ..... 08 - 14
078 - 084 ..... 09 - 14
084 - 090 ..... 10 - 14
091 - 095 ..... 11 - 14
095 - 099 ..... 12 - 14
100 - 100 ..... 12
The last two floors for any bracket always take 14 drops to test (except for 100-th floor). I didn't sum these numbers vertically but went "across" by observing that 2*14 is always there for all 11 drops. This is also true for 13 and 12. However, the rest of the numbers 2 through 11 disappear one by one for each consecutive bracket as you move up the building. It's seen in the table above.
Why did I divide by 100? Ah, I see. You count an extra outcome when no eggs break at all. Which means that the building isn't tall enough. 101. But then I would get 1035/101 = 10.24752475.
I wonder where I've lost 10 attempts?
|
| « Last Edit: Jan 6th, 2014, 10:52am by rloginunix » |
IP Logged |
|
|
|
antkor
Newbie
Posts: 30
|
|
Re: Egg Dropping
« Reply #43 on: Jan 6th, 2014, 1:43pm » |
Quote Modify
|
on Jan 6th, 2014, 10:50am, rloginunix wrote:My testing floors were 14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99 and 100.
The first column defines a bracket - a range of floors and the second column is the number of drops it takes to tell with certainty that the current floor in the current bracket really hates eggs. Since the number of drops from one floor to another within the bracket only differs by one I only give the number of drops for the initial floor and the number of drops for the last floor in the current bracket - a range in other words:
001 - 014 ..... 02 - 14
015 - 027 ..... 03 - 14
028 - 039 ..... 04 - 14
040 - 050 ..... 05 - 14
051 - 060 ..... 06 - 14
061 - 069 ..... 07 - 14
070 - 077 ..... 08 - 14
078 - 084 ..... 09 - 14
084 - 090 ..... 10 - 14
091 - 095 ..... 11 - 14
095 - 099 ..... 12 - 14
100 - 100 ..... 12
The last two floors for any bracket always take 14 drops to test (except for 100-th floor). I didn't sum these numbers vertically but went "across" by observing that 2*14 is always there for all 11 drops. This is also true for 13 and 12. However, the rest of the numbers 2 through 11 disappear one by one for each consecutive bracket as you move up the building. It's seen in the table above.
Why did I divide by 100? Ah, I see. You count an extra outcome when no eggs break at all. Which means that the building isn't tall enough. 101. But then I would get 1035/101 = 10.24752475.
I wonder where I've lost 10 attempts? |
|
the testing floors you chose are not the ones that give the lowest average value. you can alter them a bit near the end.
Grimbal how did you get your result?
|
|
IP Logged |
|
|
|
rloginunix
Uberpuzzler
Posts: 1029
|
|
Re: Egg Dropping
« Reply #44 on: Jan 6th, 2014, 6:38pm » |
Quote Modify
|
I have found the discrepancy by figuring out Grimbal's testing scheme: 9,22, 34, 45, 55, 64, 72, 79, 85, 90, 94, 97, 99, 100.
From that scheme the table I (and Grimbal probably) got is (the first column is the floors range, the second column is the total number of drops for that range):
001 - 009 ..... 58
010 - 022 ..... 116
023 - 034 ..... 113
035 - 045 ..... 109
046 - 055 ..... 104
056 - 064 ..... 98
065 - 072 ..... 91
073 - 079 ..... 83
080 - 085 ..... 74
086 - 090 ..... 64
091 - 094 ..... 53
095 - 097 ..... 41
098 - 099 ..... 27
100 - 100 ..... 14
The sum total for these numbers is 1045.
The only difference I see is the number of steps: 14 vs 12. But the basic idea is still the same. Grimbal simply shifted the entire ladder of the scheme I used down by 5 floors.
Yes, antkor, the scheme I used is not the optimal one for the average number of drops question. It's just a starting point. I'm kinda thinking out loud.
Actually it's a good thing Grimbal used a different testing scheme. It made me go back and recalculate my numbers. Except that this time I wasn't lazy and did it the right way - bracket by bracket and I have found something interesting. I will definitely share it with you guys tomorrow. Sorry, I'm dead tired right now, long day. The weather has been crazy and tomorrow morning's commute will be nuts.
Good night everyone.
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Egg Dropping
« Reply #45 on: Jan 7th, 2014, 10:10am » |
Quote Modify
|
I found 2 equivalent subsets for the first egg:
{13, 25, 36, 46, 55, 64, 72, 79, 85, 90, 94, 97, 99, 100}
and
{14, 27, 39, 50, 60, 69, 77, 84, 90, 94, 97, 99 }
I found them programmatically.
|
|
IP Logged |
|
|
|
rloginunix
Uberpuzzler
Posts: 1029
|
|
Re: Egg Dropping
« Reply #46 on: Jan 7th, 2014, 10:19am » |
Quote Modify
|
Using the 12-step testing scheme as a working model I did the totals for each bracket. The first column is the test number, the second column is the bracket (floors range), the third column is the total number of drops. Since the term 14 shows up twice for each bracket I kept one term out of the sum (by adding it explicitly) and here's what I've got:
01 .... 001 - 014 .... 104 + 14 = 118
02 .... 015 - 027 .... 102 + 14 = 116
03 .... 028 - 039 .... 99 + 14 = 113
04 .... 040 - 050 .... 95 + 14 = 109
05 .... 051 - 060 .... 90 + 14 = 104
06 .... 061 - 069 .... 84 + 14 = 98
07 .... 070 - 077 .... 77 + 14 = 91
08 .... 078 - 084 .... 69 + 14 = 83
09 .... 085 - 090 .... 60 + 14 = 74
10 .... 091 - 095 .... 50 + 14 = 64
11 .... 096 - 099 .... 39 + 14 = 53
12 .... 100 - 100 .... 12
The sum total for all the drops is 1035.
We are asked to optimize an average or to minimize a fraction. One way to minimize a fraction is to maximize its denominator. In this case we can't do it - the number of outcomes can't be changed. Hence our only chance is to minimize the sum. The sum is composite. It has 11 terms each of which is 14 while the rest of the terms (except the last one) look like the original testing floor numbers in reverse.
There's a big drop between the brackets 11 and 12.
I think that to minimize that sum we should look towards the very top of the building (last floors) because any rearrangement has to keep the number of brackets at its minimum. If we do such rearrangement early on we will increase that number. I tried the scheme that starts at floor 13 and it didn't work out.
I also tried to get rid of double fourteens in such a way that the number of brackets remains at 12 changing the scheme at the very end: ..., 89, 93, 96, 98, 99, 100 but the sum total of all the drops remained 1035.
Need to try something else.
(Edit: fixed a typo in the table, was 084 for the bracket 09, now 085)
|
| « Last Edit: Jan 7th, 2014, 1:58pm by rloginunix » |
IP Logged |
|
|
|
rloginunix
Uberpuzzler
Posts: 1029
|
|
Re: Egg Dropping
« Reply #47 on: Jan 7th, 2014, 10:22am » |
Quote Modify
|
This if funny.
When I started composing my reply there were no new posts.
After I hit "post" Grimbal's post showed up.
Go figure.
|
|
IP Logged |
|
|
|
rloginunix
Uberpuzzler
Posts: 1029
|
|
Re: Egg Dropping
« Reply #48 on: Jan 7th, 2014, 2:05pm » |
Quote Modify
|
Guys, just to clarify.
The scenario that no eggs break at all is still on the table, right?
In other words we must test all 100 floors.
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Egg Dropping
« Reply #49 on: Jan 7th, 2014, 2:58pm » |
Quote Modify
|
That is what I assumed.
So if you get 1035 for 100 floors, you still have to add 12 drops for the case 101. You get 1047/101.
(By the way, I was reasoning in terms of the number of floors that the egg resists. So I am considering numbers 0 to 100.)
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print