Author 
Topic: Egg Dropping (Read 29052 times) 

rloginunix
Uberpuzzler
Posts: 1026


Re: Egg Dropping
« Reply #50 on: Jan 7^{th}, 2014, 5:05pm » 
Quote Modify

I see. I was reasoning in terms that the floor is primary while the egg is secondary. What is the floor number thrown from which an egg shatters. So I numbered the floors 1 through 100. That's 100 possible outcomes  one shattered egg for each floor. If, following a testing scheme, by throwing the first egg from the 100th floor we observe that the egg does not shatter we conclude that the building isn't tall enough for these particular eggs. Plus one for the outcomes for a total of 101. Following this logic and using the 12step testing scheme (I'll post how I found it later) we get (test number, floors range, total number of drops): 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 For the 11th bracket test (floors 96 through 99) we get (floor number, drop number that shatters the egg): 96 12 97 13 98 14 99 14 In more detail. 11th drop shatters the first egg at the 99th floor. Use the second egg. 12th drop  floor 96 shatters the egg. 13th drop  floor 97 shatters the egg. 14th drop  floor 98 shatters the egg. If by the 14th drop off of the floor 98 the second egg does not shatter we conclude (after 14 drops) that floor 99 is bad. If floor 99 on the 11th test does not shatter the first egg we execute the 12th and final drop from the floor 100. Two outcomes. The first egg shatters  we conclude that after 12 drops floor 100 is bad and we do not need the second egg. Otherwise  the first egg does not shatter  after the same 12 drops we conclude with certainty that this building is not tall enough to shatter any eggs. Based on that logic I've got two testing schemes that I hope minimize the average number of drops. Please see the next post.


IP Logged 



rloginunix
Uberpuzzler
Posts: 1026


Re: Egg Dropping
« Reply #51 on: Jan 7^{th}, 2014, 5:42pm » 
Quote Modify

The two schemes I've found are: 1). 14, 27, 39, 50, 60, 69, 77, 84, 89, 94, 98, 100 2). 14, 27, 39, 50, 60, 69, 77, 84, 89, 93, 97, 100 My key minimization idea was to get rid of the double 14s at the end of each bracket. However, we can't do it haphazardly. As we can see the number of floors in each bracket diminishes by one as we go up. The 11th bracket test has 4 floors to deal with. So the next, 12th, bracket test has the room for 4  1 = 3 floors but only uses 1  the 100th floor. So I reasoned let's squeeze something in the 12th bracket test in the attempt to minimize the total sum. Why only the sum has to be minimized I reasoned in the previous posts. So for scheme 1) I wrote down the last four tests and moved the last floor (90) from the 9th test into the 10th. I moved the last floor (95) from the 10th test into the 11th. And I moved the last floor (99) from the 11th test into the 12th: 85 10 .......... 90 11 86 11 .......... 91 12 .......... 95 12 87 12 .......... 92 13 .......... 96 13 88 13 .......... 93 14 .......... 97 14 .......... 99 13 89 13 .......... 94 14 .......... 98 14 .......... 100 13 These four brackets total 202 drops which is one less than the original sum of 203. It comes at the expense of the increased number of tests. 13 now vs 12 then. In other words for the worst case scenario the optimized number of tests is 12 (or 14 for a 105story building) while for the average number of drops scenario we get to judge about the 99th or 100th floors or the entire building in 13 drops. Scheme 2) yields the same intermediate sum of 202. The total number I get then is 1034. Divided by 101 it's 10.237623. Divided by 100 it's 10.34. Now, as you can see I don't have a rigorous mathematical proof that this indeed is the minimum. From the experimentation I've found a testing scheme that yields a smaller average than the original one.


IP Logged 



Grimbal
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 7408


Re: Egg Dropping
« Reply #52 on: Jan 8^{th}, 2014, 11:36am » 
Quote Modify

Why do you divide by 101 if you consider only 100 different cases?


IP Logged 



rloginunix
Uberpuzzler
Posts: 1026


Re: Egg Dropping
« Reply #53 on: Jan 8^{th}, 2014, 12:24pm » 
Quote Modify

I did two divisions just in case. Sorry if it caused any confusion. At first my understanding of the problem was "one of the floors Must be bad". In that case I reasoned there can be only 100 possible outcomes. One for each floor (numbered 1 through 100). In that case we can stop the testing process at the floor 99. Because if we got up there and the first egg did not shatter then, since we know that it must, we can safely assume that the 100th Will shatter it. And in any case there are 100 possible outcomes and we should divide by 100. Later on I realized that I'm likely misinterpreting the given initial conditions of the problem and I asked the question "can it so happen that no eggs break at all"? The answer is yes. Can't assume anything. Hence we must test all the floors without exception. If we've gotten to the 99th floor and the first egg didn't break we still must drop it from the 100th floor. It may or may not break. In either case we have a scenario "a floor" is bad. That's 1 out of 100 for 100 possible outcomes. Or "no floors are bad"  the first egg survived the drop form the 100th floor. In which case I add one to the number of outcomes. Hence the division by 101. Sorry again if I caused the confusion. Did I commit programmer's favorite "off by one" error? (Edit: changed "we've got" to "we've gotten".)

« Last Edit: Jan 8^{th}, 2014, 12:32pm by rloginunix » 
IP Logged 



Grimbal
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 7408


Re: Egg Dropping
« Reply #54 on: Jan 9^{th}, 2014, 2:51pm » 
Quote Modify

Note that if you consider that the egg is known to break somewhere, then it means it breaks on floor 100. The result is that you get the same problem with the remaining 99 floors and none of them is safe.


IP Logged 



rloginunix
Uberpuzzler
Posts: 1026


Re: Egg Dropping
« Reply #55 on: Jan 10^{th}, 2014, 8:42am » 
Quote Modify

Thank you for the hint, Grimbal. I got sloppy with the definition or the meaning of average. Averaging by itself is meaningless unless the parameter over which to average is given. Are we calculating an average temperature per hour, per day, per week, per month, etc? antkor's question was "find the minimum average value of drops". I guess by "value" he meant "number". So then it is an average number of drops per what? A reasonable default meaning can be "per floor". Then we should divide by 100. Then the answer is 1034/100 = 10.34. I'm easy, guys. Don't feel like splitting hairs. May be we should ask antkor what was the author's intended meaning of the average number of drops.


IP Logged 



rloginunix
Uberpuzzler
Posts: 1026


Re: Egg Dropping
« Reply #56 on: Jan 10^{th}, 2014, 11:16am » 
Quote Modify

Found a new low reasoning thus. My original attempt to get rid of double 14s worked for the 9th bracket test. I've tried the same idea for the lower brackets but it didn't work. I actually got a higher sum total. Now I tried it from the other end. If we move just one floor, 99, from the 11th bracket test to the 12th bracket test we get: 96 12 97 13 ..... 99 13 98 13 ..... 100 13 That sum total is 38 + 26 = 64. In the original testing scheme it's 53 + 12 = 65. One drop saving. So I said, OK, if we keep moving towards the 9th bracket test (the first one that introduced some savings) what will happen? Apply this idea starting from the 10th bracket test and move floors 95, 98 and 99: 91 11 92 12 ..... 95 12 ..... 98 13 93 13 ..... 96 13 ..... 99 14 94 13 ..... 97 13 ..... 100 14 The sum total for that group is 128 vs the original 129. One drop saving. Now we have a double 14 in the last bracket. Get rid of it by splitting the 12th bracket test further: 91 11 92 12 ..... 95 12 93 13 ..... 96 13 ..... 98 13 94 13 ..... 97 13 ..... 99 13 ..... 100 13 This is basically a show of 13s and the sum total is 126. Three drops saving. 1035  3 = 1032. And the scheme is: 14, 27, 39, 50, 60, 69, 77, 84, 90, 94, 97, 99, 100 Now we've bracketed the new low of 1032 between two previous lows of 1034. I wonder if this is it or it can be improved even more. (Edit: was double checking my math and found a bug. Was subtracting 3 from 1034. That was wrong. Must subtract from 1035.)

« Last Edit: Jan 10^{th}, 2014, 3:58pm by rloginunix » 
IP Logged 



antkor
Newbie
Posts: 30


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

you are correct!!! this is the minimum sum you can get (well, you can get 1031 as well but i don't remember which floors you pick but i can check an old excel file i have upon your request. However, in that case, you need to pick 14 floors instead of 13). As far as i know, the original problem stated somethhing like: you need to find the highest floor that the eggs don't break if they are dropped from there, but still, you cannot assume that an egg will break for sure, so you have to consider 101 scenarios. So, that would give you (1032+13)/101. If you try with the sum of 1031 then you pick 14 trial floors so the final sum is again 1045/101. That means that the solution is not unique. After floor 84 you can pick either floor 89 or floor 90 and with some modifications you get the same result. Well done! I think this variation of the problem is more difficult than the classic one which only asks for the minimum number of drops.


IP Logged 



rloginunix
Uberpuzzler
Posts: 1026


Re: Egg Dropping
« Reply #58 on: Jan 11^{th}, 2014, 9:04pm » 
Quote Modify

Thank you for your post, antkor. I did so much math with this one my fingers are bleeding. I see I kept forgetting to add 13 to my totals. Dah! The test for the 100th floor now moved to the 13th bracket so of course 1032 + 13 = 1045. 101 outcomes. So 1045/101 = 10.3465. No need to look anything up, antkor. I went back and checked that Grimbal, as usual, had the correct answer. He came up with two schemes. One is based on 14 steps: 13, 25, 36, 46, 55, 64, 72, 79, 85, 90, 94, 97, 99, 100 And the other is the 13step one: 14, 27, 39, 50, 60, 69, 77, 84, 90, 94, 97, 99, 100 Both yield the same average. To sum up. This was computationally intensive. My original 10story building sample analysis was not useful. My idea of rearranging the floors and staying within the 12step testing scheme didn't work out. What did work is the idea of getting rid of double 14s. And by way of reasoning alone I doubt I would've suspected there are multiple schemes that minimize the average. So I guess computers do come in handy once in a while. Thanks again, antkor.


IP Logged 



antkor
Newbie
Posts: 30


Re: Egg Dropping
« Reply #59 on: Jan 13^{th}, 2014, 6:32am » 
Quote Modify

thank you too for your good words! the problem in that form is sure challenging and the reason for that is the many little but crucial details it has. for example, the consideration of 101 cases (and not forgetting to add the drops for the 101st case to the sum), the need to get rid of double 14s where possible and most importantly the fact that the solution for the lowest average is not unique. The last detail mentioned above is the most tricky one as it may not come to mind and one can search for ages without finding the unique solution, because there isn't any. I could have made the problem more clear if i had added the following to the instructions: You know that the eggs break for sure if dropped from a height greater than the 100th floor, but you have no other clues about their resistance (meaning they can be dropped from the 100th floor without breaking). However, I didn't add it intentionally because i wanted to make it a little bit harder, but i caused confusion instead.


IP Logged 



rloginunix
Uberpuzzler
Posts: 1026


Re: Egg Dropping
« Reply #60 on: Jan 13^{th}, 2014, 7:48pm » 
Quote Modify

Don't sweat it antkor. Small potatoes. We have a bigger fish to fry. My thought was if I can reason my way through for the worst case scenario can I do the same for the average case? So bare with me. Here's my search for the worst case solution (credits due to Mr. Fingas). 2 eggs, 100 floors, no assumptions. 1 egg, 100 floors. There's no symmetry in this problem. We can't climb to the 100th floor right away and drop the egg from there. If the egg shatters we still have no absolute certainty that that was the Lowest floor that breaks an egg. May be the 5th floor would've done the same? Conclusion  must start from the current lowest good boundary and move up one floor at a time. Which makes sense  the spirit of the problem is to test or visit each floor and now we've deduced that with one egg it must be done in one direction only. 2 eggs, 100 floors. We break the search into two parts  bracketing and exacting. With the first egg we create a bracket whose left border marks the floor that's not high enough to shatter an egg and whose right border marks the floor that guarantees to shatter an egg. The right bracket floor may or may not be it and that's why we need the second egg. With the second egg we find the exact floor. As per 1egg primitive case we know that we have to start at the left bracket and go up one floor at a time. If the second egg shatters it marks the spot if not  the first egg does. If the first egg never shatters the building isn't tall enough  no bad floor. The initial floor is 50. The first egg shatters at 100. 2 tests. We have to start our testing with the second egg from the 51st floor going up one at a time. 49 floors total. 49 + 2 = 51 tests. The initial floor is 25. The first egg shatters at 100. 4 tests. We proceed from the 76th floor with the second egg up one floor at a time. 24 floors total. 24 + 4 = 28 tests. The initial floor is 20. The first egg shatters at 100. 5 tests. We proceed from the 81st floor with the second egg up one floor at a time. 19 floors total. 19 + 5 = 24 tests. The initial floor is 10. The first egg shatters at 100. 10 tests. We proceed from the 91st floor with the second egg up one floor at a time. 9 floors total. 10 + 9 = 19 tests. The pattern emerges. Expressing the number of tests N as a function of the initial floor x we get: N = f(x) = 100/x + x  1 To find its minimum we take the first derivative and equate it to 0: f'(x) = 100/x^2 + 1 = 0 x^2 = 100 x = 10 or the square root of the building's height. So it looks like that if we start our tests at the 10th floor and proceed up on nonbreakages 10 floors at a time we get the smallest number of tests possible. [edit] Corrected the spelling mistake, clime became climb. [/edit]

« Last Edit: Feb 22^{nd}, 2014, 10:11am by rloginunix » 
IP Logged 



rloginunix
Uberpuzzler
Posts: 1026


Re: Egg Dropping
« Reply #61 on: Jan 13^{th}, 2014, 7:52pm » 
Quote Modify

Mr. Fingas suggested that 19 isn't the optimal answer. How can we find the optimal one? More importantly Why the above scheme is not the optimal one? Though calculus doesn't lie, out of curiosity I decided to see what the numbers look like if we start the testing process at various floors and proceed with the same step bracketing. Here I interpreted worst case as relative to the current testing scheme because the original question is "what is the largest number of egg drops you would ever have to do to find the right floor?", emphasis is on "ever". In other words whatever scheme you choose the bad floor has to be the most inconvenient one. For example, if we start at floor 8 then in 12 8floor brackets we get to the 96th floor where the first egg shatters. Here I assumed that the worst case scenario is that the 96th floor is bad. How many more second egg tests do we have to make in this case? 7 more  from the 89th floor all the way up to and including the 95th floor. I've compiled a twocolumn table. The first column is the initial floor number and the second column is the total number of tests: 16 21 15 20 14 20 13 19 12 19 11 19 10 19 09 19 08 19 07 20 06 21 As was expected number 19 rings as a true minimum for a narrow band of floors 8 through 13. It flips at the 7th floor from below and at the 14th floor from above. In the next table I decided to keep the intermediate results. I looked at the worst case scenario for each 10based bracket. For example, for the 10th floor I assumed that the 10th floor is bad. For the 20th floor  the 20th floor is bad. For the 30th floor  the 30th floor is bad and so on. The first column is the bracketing floor number, the second column is the number of bracketing tests done so far, the third column is the number of exacting tests needed and the last column is their sum since that captures the total number of tests required: 010 01 + 9 = 10 020 02 + 9 = 11 030 03 + 9 = 12 040 04 + 9 = 13 050 05 + 9 = 14 060 06 + 9 = 15 070 07 + 9 = 16 080 08 + 9 = 17 090 09 + 9 = 18 100 10 + 9 = 19 From the table above we see that though the number of the exacting tests remains the same, 9, the number of the bracketing tests grows from the best worst case, 10, to the worst worst case, 19.


IP Logged 



rloginunix
Uberpuzzler
Posts: 1026


Re: Egg Dropping
« Reply #62 on: Jan 13^{th}, 2014, 7:56pm » 
Quote Modify

My thought was that in the early worst cases we Underdo some tests while in the later worst cases we Overdo them. And here lies the minimization opportunity. If we pair up the furtherst numbers relative to an imaginary middle: 10 and 19, 11 and 18, 12 and 17, 13 and 16, etc, they all add up to the same number 29. My thought was that the only simplest way I can optimize the current solution is by making it the same for all the brackets or all the worst case scenarios. Whether it Is the minimum remains to be proven. My hunch was that the number should be close to a simple arithmetic average of 10 and 19. 10 + 19 = 29 over 2 is 14.5. Can't have fractions. Must have whole numbers. Is it 14 or 15? Assume it's 15. It really doesn't matter  need just a number to work with. Then if the number of the bracketing tests grows by 1 then the number of the exacting tests must diminish by 1 in order for the sum to remain constant. In other words for the initial bracketing floor the sum must look like 1 + 14 = 15, for the second bracketing floor it must be 2 + 13 = 15, for the third bracketing floor it must be 3 + 12 = 15, for the forth: 4 + 11 = 15, fifth: 5 + 10 = 15 and so on. In more detail. If the initial bracketing test at the 15th floor doesn't shatter the first egg we move up not a constant amount of floors but the amount of floors required to keep the sum 2 + x = 15 constant. 2 because that would be the bracketing test number. And if that second test does shatter the first egg we would start at the floor 16 and go up one floor at a time 15  2 = 13, that's 13 times all the way to the 28th floor. Which means that we start the second bracketing test at the 15 + 13 + 1 = 29th floor and so on. The third bracketing test would start at 15  3 = 12, 29 + 12 + 1 = 42nd floor. The forth bracketing test would start at 15  4 = 11, 42 + 11 + 1 = 54th floor, etc. Very similar to Mr. Fingas's idea but without guessing how do we find exactly what the initial testing floor is? We can now do some solid math. Let the initial floor of the first bracketing test be f1. The second bracketing test will be at the floor f2 = f1  1. The third  at f3 = f2  1 = f1  1  1 = f1  2. The forth  at f4 = f3  1 = f1  3 and so on. For the ith test we get fi = f1  i + 1. Since we have to test all the floors in the building the sum total of all the fi terms must be at least 100, may be more: Sum i=[1,N] (f1  i + 1 ) >= 100 I will omitt the range for now since it's awkward: Sum = Sum(f1  i + 1) = Sum f1  Sum i + Sum 1 Sum f1 = N*f1 Sum i = N(N + 1)/2 Sum 1 = N Sum = N*f1  N(N + 1)/2 + N >= 100 Let's assume the equality for now: N*f1  N(N + 1)/2 + N = 100 We have one equation and two variables: N and f1. In the constant bracketing step scheme N and f1 were locked into a formula N = 100/f1 + f1  1. In this case however we see that the total number of tests is the same for any bracket. And if it's the same for all it must be so for the initial one: N = f1. Hence we rewrite our equation thus: f1^2  f1^2/2  f1/2 + f1  100 = 0 f1^2/2 + f1/2  100 = 0 f1^2 + f1  200 = 0 f1_(1,2) = (1 + sqrt(1 + 800))/2 f1_1 = (1  28.3)/2 = 14.65 f1_2 = (1 + 28.3)/2 = 13.65


IP Logged 



rloginunix
Uberpuzzler
Posts: 1026


Re: Egg Dropping
« Reply #63 on: Jan 13^{th}, 2014, 7:59pm » 
Quote Modify

Throw the negative root out. What's left is f1 = 13.65. Round it up because we really have our original Inequaltiy as > or = to. So the answer is f1 = 14 and the testing scheme is: 14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99, 102, 104, 105 So with two eggs we can test a 105story building in 14 tests or a 100story building in 12 tests. Generalizing for N stories we get: f1^2 + f1 2N = 0 Solve it for f1. We can also rewrite this equation as: f1(f1 + 1)/2 = N The algebraic interpretation of f1. It is the smallest last term of an arithmetic progression with the initial term 1 and a common difference 1 whose sum is at least N. That's it for today. I will post my proof shortly.


IP Logged 



rloginunix
Uberpuzzler
Posts: 1026


Re: Egg Dropping
« Reply #64 on: Jan 14^{th}, 2014, 8:38pm » 
Quote Modify

Now the proof. Let's assume that an optimal solution T exists. Then in T tests we can tell with an absolute certainty either the number of the lowest floor that breaks an egg or that this 100story building isn't tall enough to break any eggs. The outcome of the any test is binary  the egg either shatters, true or 1, or not, false or 0. In the 12coin problem we had three possible outcomes and we used the ternary numbers but here we have only two possible outcomes so let's use binary numbers. What are all the possible outcomes of all the tests performed by the time we got to the 100th floor via some algorithm? 1). Both eggs shatter. 2). One egg shatters. 3). No eggs shatter. If the egg shatters we mark the current bit as 1. If it doesn't  we mark it as 0. Then we move one bit position over to the left subject to conditions described below. The number of optimal tests T then can be represented as a string of T bits of zeros and ones. Case 1) corresponds to a binary number with T  2 zeros and 2 ones. Case 2) corresponds to a binary number with T  1 zeros and 1 one. Case 3) corresponds to a binary number with T zeros and 0 ones. However, we can't fill in the 1s as we normally would with the binary numbers. When we run out of positions for two 1s we can't add the third 1  we must jump left and start all over again because at any one time at most two bits can be set to 1. Below is a sample table of how you would fill in the bits for a 7bit string. These are not all the possible combinations but rather the limiting cases. The second column in the table below is the highest number starting from 1 you can record with at most two 1s. In the first row you have only 1 bit available, in the second  two, in the third three and so on: 0000001 ..... 1 0000011 ..... 3 0000110 ..... 6 0001100 ..... 10 0011000 ..... 15 0110000 ..... 21 1100000 ..... 28 For example, decimal 6 is 110 binary. Decimal 7 would normally be 111 but we are not allowed to have more than two 1s set at any given time. So we have to do this: 1000 and so on. As you can see we can already ask ourselves  what is the smallest number of such bits needed to record numbers 1 through 100 if only two bits can be set to 1 at any given time? If you do the simple arithmetic you'll see that that number is 14 and the pattern of an arithmetic progression shows up. However it's not very useful for generalization. So let's assume we have two distinct items. Their repetition is not allowed  it has to be just two items. No more and no less. Order matters. In any positional number system xy is not yx. Permutations. We can permute two items within T positions in P(T, 2) ways. However, now we take into account the fact that the items are identical and indistinguishable from each other. 101 will still be 101 even if we swap the ones around. So we need to reduce that number by the number of their combinations which is 2! to get C(T, 2). For the second case we get C(T, 1). And for the third case we get C(T, 0): Total number of possible outcomes = N(T) = C(T, 2) + C(T, 1) + C(T, 0) obtained via some algorithm. How do we connect the possible outcomes with the building's height? Dirichlet's or pigeonhole principle. When we conduct a series of tests according to some abstract algorithm in the end we should really get only one answer. Either the floor so and so is bad or the building isn't tall enough. So our algorithm should ideally produce at least 100 possible outcomes  one for each floor. If not. Let pigeon == floor and hole == outcome. Then according to the principle for at least one outcome(hole) there will be more than one floor(pigeon). Which translates into the loss of certainty in our case. Which is not acceptable. So the above sum must be >= 100. What's left to do now is to experimentally (that's my weak spot*) determine which T gets us to at least 100 floors: N(10) = C(10, 2) + C(10, 1) + C(10, 0) = 45 + 10 + 1 = 56  not enough N(11) = C(11, 2) + C(11, 1) + C(11, 0) = 55 + 11 + 1 = 67  not enough N(12) = C(12, 2) + C(12, 1) + C(12, 0) = 66 + 12 + 1 = 79  not enough N(13) = C(13, 2) + C(13, 1) + C(13, 0) = 78 + 13 + 1 = 92  not enough N(14) = C(14, 2) + C(14, 1) + C(14, 0) = 91 + 14 + 1 = 106  Bingo! N(15) = C(15, 2) + C(15, 1) + C(15, 0) = 105 + 15 + 1 = 121  works too but not smallest N(16) = C(16, 2) + C(16, 1) + C(16, 0) = 120 + 16 + 1 = 137  works too but not smallest We've got here by not making any assumptions about which algorithm does it. So it's safe* to say that no algorithm can take less than 14 bits to accomplish the task. All 14 bits used to the gills can count to 105 which gives us 5 extra floors or two extra tests. So for a 100story building we can do it in 12 tests. What was required to prove. * I think that "experimentally" kills the rigor. As of this writing I've studied this stuff more than two decades ago so may be I'm forgetting some formula or a theorem but I don't really remember off the top of my head what the answer for this sum in analytic functions is. If someone knows a better way  by all means feel free to step in.


IP Logged 



rloginunix
Uberpuzzler
Posts: 1026


Re: Egg Dropping
« Reply #65 on: Jan 14^{th}, 2014, 8:41pm » 
Quote Modify

And now we can generalize the above formula for N floors and K eggs: Sum i= [0, K] C(X, i) >= N which is a sum of K + 1 nCr terms and X must be solved for. For example, for 3 eggs and 100 stories we get: N( 8 ) = C(8, 3) + C(8, 2) + C(8, 1) + C(8, 0) = 56 + 28 + 8 + 1 = 93  not enough N(9) = C(9, 3) + C(9, 2) + C(9, 1) + C(9, 0) = 84 + 36 + 9 + 1 = 130  works The initial floor for the 3egg case is X. After we drop the first egg and it shatters we would have 9  1 = 8 drops left. What is the tallest building we can test in 8 drops with 2 eggs? We already know. 8*9 = 72, 72/2 = 36. So we do the first drop from the 37th floor. After the second drop of the first egg from the floor Y we would have 9  2 = 7 drops left. What is the tallest building we can test in 7 drops with 2 eggs? 7*8 = 56, 56/2 = 28. 38 + 28 = 66. So the second bracket floor is 66. If you proceed that way you will see that in 9 drops with 3 eggs you can test a 130story building: 37, 66, 88, 104, 115, 122, 126, 128, 130 For a 100story building we would get to the top in 4 drops. We would then have to test 11 floors, 89 trough 99, which is 5 tests. So with 3 eggs and 100 floors there's no savings and 9 drops it is. (Edit: changed N(eight) to N( 8 ) to get rid of smiley.)

« Last Edit: Jan 14^{th}, 2014, 8:44pm by rloginunix » 
IP Logged 



Grimbal
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 7408


Re: Egg Dropping
« Reply #66 on: Jan 16^{th}, 2014, 3:04pm » 
Quote Modify

I still wanted to tell how I solved the problem The only question in fact is where do you drop the first egg. let's call d(f,e) the minimum number of drops to test each of f different floors with e eggs. if f=0, d(f,e) = 0. else, if e=0, it is impossible. for all other cases, you drop at some level k(f,e). If it breaks, you have to test the (k1) floors below with (e1) eggs. If not, you have to test (fk) floors above with e eggs. The number of drops is  1 for each of the (f+1) possible cases  d(k1,e1) for all the cases where the egg breaks  d(fk,e) for the cases where the egg resists. The optimal k = k(f,e) is the one that minimizes the number of drops: d(f,e) = (f+1) + min[k=1..f]( d(k1,e1) + d(fk,e) ) k(f,e) = k with the min value k(100,2) = 14. So the 1st 2egg test floor is 14. k(86,2) = 13. So the 1st 2egg test floor is 14+13 = 27. k(73,2) = 12. So the 1st 2egg test floor is 27+12 = 39. etc. There are usually 2 floors with the same drop value, that is why you have multiple optimal sets of floors for droping the 1st egg. Edit: fixed typos.

« Last Edit: Jan 21^{st}, 2014, 9:09am by Grimbal » 
IP Logged 



rloginunix
Uberpuzzler
Posts: 1026


Re: Egg Dropping
« Reply #67 on: Jan 17^{th}, 2014, 8:33am » 
Quote Modify

Very concise indeed, Grimbal. Taken out of context with no prior knowledge an intuition of a rookie like me didn't take me to recursive equations at all. May be if it were an exercise in a text book under the appropriate chapter. I guess I have to brush up on them. I'm always willing to learn from the best though. Could you please explain these two lines: d(f,e) = (f+1) + min[k=1..f]( d(f1,e1) + d(fk,e) ) k(f,e) = k with the min value I followed your deduction up until here. The notation starting from "min" is not obvious to me. Does it mean smallest sum for some k or smallest k that makes the equation balance? Not really clear. Thank you in advance.


IP Logged 



Grimbal
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 7408


Re: Egg Dropping
« Reply #68 on: Jan 17^{th}, 2014, 2:20pm » 
Quote Modify

The brackets are supposed to represent subscripts k=1..f means for k going from 1 to f. d(f,e) = (f+1) + min_{k=1,2,...,f} ( d(k1,e1) + d(fk,e) ) By the way, you don't need recursion to compute it. The calculation of d(f,e) only uses values of d for smaller d and f. So you can compute all the values in a loop storing it in an array. It is also much faster. Edit: fixed typos.

« Last Edit: Jan 21^{st}, 2014, 9:08am by Grimbal » 
IP Logged 



rloginunix
Uberpuzzler
Posts: 1026


Re: Egg Dropping
« Reply #69 on: Jan 18^{th}, 2014, 11:37am » 
Quote Modify

Thank you. I've got the range notation. It was not immediately obvious to me what the operator "min" binds to. To the range, as in "lowest floor", or the sum. Now I understand it is the sum. The meaning of this line is "smallest sum for all the ks running from 1 to F", where F is the highest floor. So you're recording the minimums as you clime to higher and higher floors feeding the previous into the calculation of the next one. Until you hit the 100th floor. Is that the gist of it? (Edit: changed "If" to "Is".)

« Last Edit: Jan 18^{th}, 2014, 11:39am by rloginunix » 
IP Logged 



rmsgrey
Uberpuzzler
Gender:
Posts: 2818


Re: Egg Dropping
« Reply #70 on: Jan 21^{st}, 2014, 7:38am » 
Quote Modify

on Jan 17^{th}, 2014, 2:20pm, Grimbal wrote:The brackets are supposed to represent subscripts k=1..f means for k going from 1 to f. d(f,e) = (f+1) + min_{k=1,2,...,f} ( d(f1,e1) + d(fk,e) ) 
 If d(f,e) is the minimum number of drops required to test f floors with e eggs, then you need a different expression  d(100,2) should be rather less than 101, while your expression is going to be rather more... There also appears to be a mistake in your recursion  when the egg breaks on floor k, you want to test k1 floors with e1 eggs, not f1 floors with e1 eggs. I get: d(f,e) = 1 + min_{k=1,2,...,f}{d(k1,e1) + d(fk,e)}


IP Logged 



Grimbal
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 7408


Re: Egg Dropping
« Reply #71 on: Jan 21^{st}, 2014, 9:16am » 
Quote Modify

You are right about the recursion, I had it right, (k1) and (fk), in the beginning, then the k1 became f1. I fixed that. But I think we are not speaking about the same d(f,e). Mine is the total drops necessary to test all of the cases one after the other. The aim is to compute the average number of drops over all possible cases.

« Last Edit: Jan 21^{st}, 2014, 9:17am by Grimbal » 
IP Logged 



rloginunix
Uberpuzzler
Posts: 1026


Re: Egg Dropping
« Reply #72 on: Jan 21^{st}, 2014, 11:01am » 
Quote Modify

Reconnecting the disconnect. antkor posted an average case problem. Grimbal found 2 schemes programmatically. I found 1 by hand and semireasoning. I then shared my worst case analytic solution wondering if the same can be done for the average case. Grimbal posted his programmatic solution  for the average case. All this time, however, I thought that Grimbal is sharing his analytic solution for the worst case. So here, I unconfused myself. Grimbal's posts represent programmatic nonrecursive average case solution. Since it's nonrecursive the intermediate results must be stored somewhere so I figure there's a space cost of a 2D table of size (number of eggs)x(number of floors) is involved.


IP Logged 



