Author 
Topic: Egg Dropping (Read 32385 times) 

continuum
Newbie
Gender:
Posts: 14


Re: Egg Drop: any solutions better than this?
« Reply #25 on: Sep 19^{th}, 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 26^{th}, 2002, 12:23am » 
Quote Modify

Late to join.... The answers posted here are similar to the one I got (although I used bruteforce 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: 574


Re: Egg Dropping
« Reply #27 on: Oct 29^{th}, 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 29^{th}, 2012, 12:45am by jollytall » 
IP Logged 



rmsgrey
Uberpuzzler
Gender:
Posts: 2844


Re: Egg Dropping
« Reply #28 on: Oct 29^{th}, 2012, 7:01am » 
Quote Modify

on Oct 29^{th}, 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: 574


Re: Egg Dropping
« Reply #29 on: Oct 29^{th}, 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: 574


Re: Egg Dropping
« Reply #30 on: Nov 11^{th}, 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 3^{rd}, 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: 7517


Re: Egg Dropping
« Reply #32 on: Jan 3^{rd}, 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 4^{th}, 2014, 6:47am » 
Quote Modify

on Jan 3^{rd}, 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: 1026


Re: Egg Dropping
« Reply #34 on: Jan 4^{th}, 2014, 10:31am » 
Quote Modify

Guys, for the last three weeks or so I've been pondering the optimal 2egg 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: 7517


Re: Egg Dropping
« Reply #35 on: Jan 4^{th}, 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: 1026


Re: Egg Dropping
« Reply #36 on: Jan 4^{th}, 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: 7517


Re: Egg Dropping
« Reply #37 on: Jan 5^{th}, 2014, 2:30am » 
Quote Modify

No. I would say it is the average between the 101 possible answers.


IP Logged 



rloginunix
Uberpuzzler
Posts: 1026


Re: Egg Dropping
« Reply #38 on: Jan 5^{th}, 2014, 11:04am » 
Quote Modify

Got it. Thanks, Grimbal.


IP Logged 



rloginunix
Uberpuzzler
Posts: 1026


Re: Egg Dropping
« Reply #39 on: Jan 5^{th}, 2014, 12:01pm » 
Quote Modify

I think I'm on to something. Check out this pattern. A sample 10story 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: 01st: 2 (4, 1) 02nd: 3 (4, 1, 2) 03rd: 4 (4, 1, 2, 3) 04th: 4 (4, 1, 2, 3) 05th: 3 (4, 7, 5) 06th: 4 (4, 7, 5, 6) 07th: 4 (4, 7, 5, 6) 08th: 4 (4, 7, 9, 8 ) 09th: 4 (4, 7, 9, 8 ) 10th: 4 (4, 7, 9, 10) We see that the average number of drops for the 10story 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 100story building.


IP Logged 



rloginunix
Uberpuzzler
Posts: 1026


Re: Egg Dropping
« Reply #40 on: Jan 5^{th}, 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: 7517


Re: Egg Dropping
« Reply #41 on: Jan 6^{th}, 2014, 5:51am » 
Quote Modify

I get 1045/101 = 10.3465


IP Logged 



rloginunix
Uberpuzzler
Posts: 1026


Re: Egg Dropping
« Reply #42 on: Jan 6^{th}, 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 100th 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 6^{th}, 2014, 10:52am by rloginunix » 
IP Logged 



antkor
Newbie
Posts: 30


Re: Egg Dropping
« Reply #43 on: Jan 6^{th}, 2014, 1:43pm » 
Quote Modify

on Jan 6^{th}, 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 100th 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: 1026


Re: Egg Dropping
« Reply #44 on: Jan 6^{th}, 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: 7517


Re: Egg Dropping
« Reply #45 on: Jan 7^{th}, 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: 1026


Re: Egg Dropping
« Reply #46 on: Jan 7^{th}, 2014, 10:19am » 
Quote Modify

Using the 12step 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 7^{th}, 2014, 1:58pm by rloginunix » 
IP Logged 



rloginunix
Uberpuzzler
Posts: 1026


Re: Egg Dropping
« Reply #47 on: Jan 7^{th}, 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: 1026


Re: Egg Dropping
« Reply #48 on: Jan 7^{th}, 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: 7517


Re: Egg Dropping
« Reply #49 on: Jan 7^{th}, 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 



