Author |
Topic: Egg Dropping (Read 33260 times) |
|
rloginunix
Uberpuzzler
Posts: 1029
|
 |
Re: Egg Dropping
« Reply #50 on: Jan 7th, 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 100-th 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 12-step 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 11-th 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. 11-th drop shatters the first egg at the 99-th floor. Use the second egg. 12-th drop - floor 96 shatters the egg. 13-th drop - floor 97 shatters the egg. 14-th drop - floor 98 shatters the egg. If by the 14-th 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 11-th test does not shatter the first egg we execute the 12-th 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: 1029
|
|
Re: Egg Dropping
« Reply #51 on: Jan 7th, 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 14-s 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 11-th bracket test has 4 floors to deal with. So the next, 12-th, bracket test has the room for 4 - 1 = 3 floors but only uses 1 - the 100-th floor. So I reasoned let's squeeze something in the 12-th 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 9-th test into the 10-th. I moved the last floor (95) from the 10-th test into the 11-th. And I moved the last floor (99) from the 11-th test into the 12-th:
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 105-story building) while for the average number of drops scenario we get to judge about the 99-th or 100-th 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: 7527
|
|
Re: Egg Dropping
« Reply #52 on: Jan 8th, 2014, 11:36am » |
Quote Modify
|
Why do you divide by 101 if you consider only 100 different cases?
|
|
IP Logged |
|
|
|
rloginunix
Uberpuzzler
Posts: 1029
|
|
Re: Egg Dropping
« Reply #53 on: Jan 8th, 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 100-th 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 99-th floor and the first egg didn't break we still must drop it from the 100-th 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 100-th 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 8th, 2014, 12:32pm by rloginunix » |
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Egg Dropping
« Reply #54 on: Jan 9th, 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: 1029
|
|
Re: Egg Dropping
« Reply #55 on: Jan 10th, 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: 1029
|
|
Re: Egg Dropping
« Reply #56 on: Jan 10th, 2014, 11:16am » |
Quote Modify
|
Found a new low reasoning thus.
My original attempt to get rid of double 14-s worked for the 9-th 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 11-th bracket test to the 12-th 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 9-th bracket test (the first one that introduced some savings) what will happen?
Apply this idea starting from the 10-th 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 12-th 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 13-s 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 10th, 2014, 3:58pm by rloginunix » |
IP Logged |
|
|
|
antkor
Newbie
Posts: 30
|
|
Re: Egg Dropping
« Reply #57 on: Jan 11th, 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: 1029
|
|
Re: Egg Dropping
« Reply #58 on: Jan 11th, 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 100-th floor now moved to the 13-th 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 13-step 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 10-story building sample analysis was not useful. My idea of rearranging the floors and staying within the 12-step testing scheme didn't work out. What did work is the idea of getting rid of double 14-s. 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 13th, 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: 1029
|
|
Re: Egg Dropping
« Reply #60 on: Jan 13th, 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 100-th 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 5-th 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 1-egg 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 51-st 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 76-th 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 81-st 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 91-st 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 10-th floor and proceed up on non-breakages 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 22nd, 2014, 10:11am by rloginunix » |
IP Logged |
|
|
|
rloginunix
Uberpuzzler
Posts: 1029
|
|
Re: Egg Dropping
« Reply #61 on: Jan 13th, 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 8-floor brackets we get to the 96-th floor where the first egg shatters. Here I assumed that the worst case scenario is that the 96-th floor is bad. How many more second egg tests do we have to make in this case? 7 more - from the 89-th floor all the way up to and including the 95-th floor. I've compiled a two-column 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 7-th floor from below and at the 14-th floor from above.
In the next table I decided to keep the intermediate results. I looked at the worst case scenario for each 10-based bracket.
For example, for the 10-th floor I assumed that the 10-th floor is bad. For the 20-th floor - the 20-th floor is bad. For the 30-th floor - the 30-th 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: 1029
|
|
Re: Egg Dropping
« Reply #62 on: Jan 13th, 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 15-th 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 28-th floor. Which means that we start the second bracketing test at the 15 + 13 + 1 = 29-th floor and so on. The third bracketing test would start at 15 - 3 = 12, 29 + 12 + 1 = 42-nd floor. The forth bracketing test would start at 15 - 4 = 11, 42 + 11 + 1 = 54-th 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 i-th 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: 1029
|
|
Re: Egg Dropping
« Reply #63 on: Jan 13th, 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 105-story building in 14 tests or a 100-story 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: 1029
|
|
Re: Egg Dropping
« Reply #64 on: Jan 14th, 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 100-story 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 12-coin 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 100-th 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 1-s as we normally would with the binary numbers. When we run out of positions for two 1-s 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 7-bit 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 1-s. 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 1-s 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 100-story 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: 1029
|
|
Re: Egg Dropping
« Reply #65 on: Jan 14th, 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 3-egg 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 37-th 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 130-story building:
37, 66, 88, 104, 115, 122, 126, 128, 130
For a 100-story 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 14th, 2014, 8:44pm by rloginunix » |
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Egg Dropping
« Reply #66 on: Jan 16th, 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 (k-1) floors below with (e-1) eggs. If not, you have to test (f-k) floors above with e eggs.
The number of drops is
- 1 for each of the (f+1) possible cases
- d(k-1,e-1) for all the cases where the egg breaks
- d(f-k,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(k-1,e-1) + d(f-k,e) )
k(f,e) = k with the min value
k(100,2) = 14. So the 1st 2-egg test floor is 14.
k(86,2) = 13. So the 1st 2-egg test floor is 14+13 = 27.
k(73,2) = 12. So the 1st 2-egg 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 21st, 2014, 9:09am by Grimbal » |
IP Logged |
|
|
|
rloginunix
Uberpuzzler
Posts: 1029
|
|
Re: Egg Dropping
« Reply #67 on: Jan 17th, 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(f-1,e-1) + d(f-k,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: 7527
|
|
Re: Egg Dropping
« Reply #68 on: Jan 17th, 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) + mink=1,2,...,f ( d(k-1,e-1) + d(f-k,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 21st, 2014, 9:08am by Grimbal » |
IP Logged |
|
|
|
rloginunix
Uberpuzzler
Posts: 1029
|
|
Re: Egg Dropping
« Reply #69 on: Jan 18th, 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 k-s 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 100-th floor. Is that the gist of it?
(Edit: changed "If" to "Is".)
|
| « Last Edit: Jan 18th, 2014, 11:39am by rloginunix » |
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
    
Gender:
Posts: 2872
|
|
Re: Egg Dropping
« Reply #70 on: Jan 21st, 2014, 7:38am » |
Quote Modify
|
on Jan 17th, 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) + mink=1,2,...,f ( d(f-1,e-1) + d(f-k,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 k-1 floors with e-1 eggs, not f-1 floors with e-1 eggs.
I get:
d(f,e) = 1 + mink=1,2,...,f{d(k-1,e-1) + d(f-k,e)}
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Egg Dropping
« Reply #71 on: Jan 21st, 2014, 9:16am » |
Quote Modify
|
You are right about the recursion, I had it right, (k-1) and (f-k), in the beginning, then the k-1 became f-1.
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 21st, 2014, 9:17am by Grimbal » |
IP Logged |
|
|
|
rloginunix
Uberpuzzler
Posts: 1029
|
|
Re: Egg Dropping
« Reply #72 on: Jan 21st, 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 semi-reasoning. 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 non-recursive average case solution.
Since it's non-recursive 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 |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print