wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> Egg Dropping
        
(Message started by: Trevor Squires on Jul 25^th, 2002, 4:35am)

Title: Egg Dropping
Post by Trevor Squires on Jul 25^th, 2002, 4:35am

I have no math or CS background so I have to express this in the only way I know how, sorry.

Code:

public int answer(int s)
{
int c = 0;
for (int t = 0; t < s; t += c++ + 1);
return c;
}

I won't say how I use the answer, lest I spoil it for others (or maybe I'm the only one that found this a challenge).

Is there anything better than this, if so how about a hint (rather than complete spoon feeding)?

Trevor

Title: Re: Egg Drop: any solutions better than this?
Post by Gamer555 on Jul 30^th, 2002, 9:21am

Is the famous solution the answer?

50: If breaks, do 25, if not do 75. So on, dictomizing the answer each time...

Title: Re: Egg Drop: any solutions better than this?
Post by Cze-jwin on Jul 30^th, 2002, 12:13pm

what if it breaks on 25..u have to find the exact floor or perhaps should i say the limit of the egg...?

Title: Re: Egg Drop: any solutions better than this?
Post by Chronos on Aug 15^th, 2002, 5:18pm

A simple answer which is close to optimal: Drop the first egg from 10, 20, 30, etc. until it breaks. Say it breaks on 40, but not on 30. Then, drop the second egg from 31, 32, 33, etc.

The reason that this is not completely optimal:

If the first egg does not break on the first few floors, we've simplified the problem. If, for instance, the first egg survives the fall from 20 feet, then we've still got two test eggs, but only 80 floors to choose from, and we can now increment by 9s instead of by 10s. Once we get below 64 floors to choose from, we can increment by 8s, etc.

Title: Re: Egg Drop: any solutions better than this?
Post by tim on Aug 15^th, 2002, 5:30pm

Chronos: Yes, very close.

My thought processes when I was solving it:
How many floors can the building have to always succeed with a maximum of 1 drop? 2 drops? N drops?

More general (and a bit nastier) problem: What if you have K eggs?

Title: Re: Egg Drop: any solutions better than this?
Post by Eric Yeh on Aug 16^th, 2002, 5:55am

Ye -- that was a problem I posted in the generalization. Also expand to n floors.

Title: Re: Egg Drop: any solutions better than this?
Post by Chronos on Aug 17^th, 2002, 11:21am

OK, my solution for N floors and two eggs: For the first egg, increment the floor by the square root of the number of floors remaining, rounded up. For the second, increment by one at a time.

Now, for more eggs: We should be able to proceed inductively, since once the first egg is broken, the problem is reduced to the one with one less egg. But I'm not sure how, in general, to increment the first egg for more than two eggs (for that matter, I'm not certain my solution is optimal for two eggs, and it looks like tim has a better one). I am, at least, reasonably sure that in the many-floor limit, my solution tends towards optimality.

One thing that we can say for certain about the many-egg case, is that given any number of floors, for a sufficient number of eggs our strategy must turn into a straightforward binary search.

Title: Re: Egg Drop: any solutions better than this?
Post by Pietro on Aug 26^th, 2002, 2:50pm

I think an important point that should be cleared up is whether optimality refers to [/i]average[i] or [/i]worst-case[i] optimality. From the other posts, I assume it's worst-case. I'll write some more about this later.
Trevor, it appears to me that your function answer(s) returns the least integer c such that c(c+1)/2 is greater than or equal to s. An analytic way to express this would be:

c = ceiling( -1/2 + sqrt(2s + 1/4) ).

I'm not sure what algorithm you would use to achieve this number of drops, but I'll be thinking about it over dinner! :)

Title: Re: Egg Drop: any solutions better than this?
Post by James Fingas on Aug 27^th, 2002, 8:33am

I think it's good to consider how we transition from the simple solution (drop egg 1 in 10-floor increments, then drop egg 2 in 1-floor increments) to the suggestions that we use the square root of the number of floors.

The reason that the simpler solution is not optimal is that the worst case is 18 drops: if egg 1 breaks on floor 90, then we may need 9 drops of egg 2 to find out the exact floor for egg 2. Therefore, we can speed things up by going up to floor 18 for the first drop of egg 1, then up 17 more floors for the second drop of egg 1, without changing the worst case. You get a pyramid type of answer, where each drop of egg 1 gets closer to the last drop.

This is one problem where you can generate an optimal answer through composition (this will apply to N eggs as well)
Work from a fixed number of drops and a fixed number of eggs to find out how many floors you can test that way, and then you can compose your answer like this:

maxfloors( int eggs, int drops ) {
if (eggs == 1) // when there's only one egg, the answer is simple
return drops;

if (eggs >= drops ) // when we have enough eggs, we can do a binary search!
return (1 << drops) - 1;

return maxfloors( eggs, drops - 1 ) //the first egg survives
+ 1 // count the floor we drop the first egg from
+ maxfloors( eggs - 1, drops - 1 ); //the first egg breaks
}

To find out how many drops for an M-story building, you
see if you can do it in 1 drop, then 2 drops, etc. But maybe there's a better way to test ... maybe we can make an algorithm that will work out the best sequence of drops to test to find the minimum number of drops ;) ...

Title: Re: Egg Drop: any solutions better than this?
Post by tim on Aug 27^th, 2002, 9:24pm

Let's write that mathematically rather than computationally:

Let N(d, e) = number of floor distinguishable with d drops and e eggs.
N(d,0) = N(0,e) = 0, since we can't check any floors without available eggs and drops.
N(d+1,e) = 1 + N(d,e) + N(d,e-1), as James has posted.

If you dropped the "1 + " from the last line, this recurrence relation should look suspiciously familiar to anyone who has ever done any work with combinations. And that's all I'm going to say ;-)

Title: Re: Egg Drop: any solutions better than this?
Post by william wu on Aug 30^th, 2002, 4:20am

Cool, same formula I got. James Fingas recently sent me an e-mail challenging me with the question of "how tall a building can you test with N eggs and M drops?" He also attached a cool graph I will reproduce here, scaled down:

http://www.ocf.berkeley.edu/~wwu/images/riddles/egg_drop_testing_graph.gif

The tallest building you can test with e eggs and d drops is defined by the recurrence relationship:

f(e,d) = f(e-1,d-1) + 1 + f(e,d-1)

brief intuitive explanation:

When you drop an egg, you figure out a floor -- that is you figure out if your egg can break on that floor. So that's where the "+1" term comes from.

If that egg cracks, you used up an egg and a drop. That explains the "f(e-1, d-1)" term.

If the egg does not crack, you used up a drop, but you still have the same number of eggs. That explains the "f(e, d-1)" term.

The relation is recursive because after using up your first drop and possibly an egg, the number of floors you can solve is 1 + the optimal number of floors you can test with your remaining resources.

Coincidentally, this dynamic programming problem was recently asked at topcoder.com during a tournament.

Title: Re: Egg Drop: any solutions better than this?
Post by tim on Sep 1^st, 2002, 5:17pm

The recurrence relation is only a stepping-stone. There is a closed-form expression:
f(e,d) = C(d,e) + 2^e - 1,
where C(n,k) is the usual combinatorial formula n! / k!(n-k)!.
Obviously it applies only for e <= d. ;)

Title: Re: Egg Drop: any solutions better than this?
Post by AlexH on Sep 1^st, 2002, 9:54pm

I'm not sure if you mean 2^e-1 or 2^e-1 in your formula, but either way I don't think it matches the recurrence relation. Maybe I've made an error so I'll try to look at it more later.

Title: Re: Egg Drop: any solutions better than this?
Post by AlexH on Sep 2^nd, 2002, 12:39am

f(d,e) = SUM_{i=1 to e} C(d,i)

In other words f(d,e) is the number of binary strings of length d containing between 1 and e 1s. This is one of those "retrospectively obvious" problems. Each possible floor must be uniquely identified by the breaking pattern of the eggs, and the best algorithm wouldn't have two breaking patterns which result in the determination of the same floor.

Title: Re: Egg Drop: any solutions better than this?
Post by KT on Sep 4^th, 2002, 12:51am

I enjoy all the deductive reasoning here, but aren't we missing the point that it takes no egg drops to answer the original question? "How high can the egg fall before it breaks?" The egg can fall forever with out breaking. It only breaks when it LANDS! If the wording of the question is in error than the egg is on the face.

Title: Re: Egg Drop: any solutions better than this?
Post by James Fingas on Sep 4^th, 2002, 9:05am

AlexH,

Cool! That's a good way to think about it!

You're off by one, however:
f(d,e) = sum_{i=1 to e}C(d,i) - 1

That is, unless you count "egg doesn't break" as a floor.

The solutions for a given number of eggs are polynomials in the number of drops. For the first few values of d, they mimic the 2^d function, as your formula predicts. For 1 egg, you get a linear function, for 2 eggs you get a quadratic, etc. Your formula also tells us that these polynomials can be used to compute partial sums of the rows of Pascal's triangle. Hmm...

Title: Re: Egg Drop: any solutions better than this?
Post by James Fingas on Sep 4^th, 2002, 9:36am

KT,
Thank you for your in-depth analysis of the problem. Your solution is only partly correct. Think of interstellar meteorite eggs which enter the earth's atmosphere and burn up. We must consider these eggs to have "broken".

Title: Re: Egg Drop: any solutions better than this?
Post by AlexH on Sep 4^th, 2002, 12:17pm

James: The formula is correct as is. The -1 you refer to is already accounted for in the exclusion of i=0 from the summation. The i=0 case occurs when no eggs break and is not counted as a floor.

If we assume that the arithmetic on these numbers is O(1) then sum of combinations can be computed in O(e) which is faster than the O(ed) table. Since the numbers grow quicky it might be better to look at bitwise complexity, which would make the sum of combinations be in general O(ed log d) versus O(ed²) for the table.

Title: Re: Egg Drop: any solutions better than this?
Post by James Fingas on Sep 5^th, 2002, 11:35am

Alex, (sorry, this said "Eric" -- he's too sneaky too, but not to blame in this particular case)

You're too sneaky for me again!

When I said polynomials, I didn't mean polynomial-time. What I meant was:

1) Fix the number of eggs at n.
2) Now express the number of testable floors as a function of the number of drops, d.
3) The solution you get is of the form a_ndⁿ + a_n-1d^n-1 + ... + a₁d + a₀
4) The solution also satisfies f(d) = 2^d for d <= n.

Title: Re: Egg Drop: any solutions better than this?
Post by AlexH on Sep 5^th, 2002, 1:26pm

Err, Eric? :P

For clarification: my second paragraph above wasn't actually in response to your comments about the solutions being polynomials in d for any fixed e (they are), I was just making an observation on computation time of the new formula vs the table method.

Title: Re: Egg Drop: any solutions better than this?
Post by James Fingas on Sep 5^th, 2002, 1:40pm

AlexH,

Right, I see what you're talking about now. I don't necessarily agree with your solution--doesn't the C(d,e) function take longer to compute than an addition?

I wonder how long it would take to compute the polynomial for the given number of eggs and evaluate it...

Title: Re: Egg Drop: any solutions better than this?
Post by AlexH on Sep 5^th, 2002, 3:10pm

The thing is we're computing the sum over i of C(d,i). If arithmetic operations are constant time then we can use
C(d,i+1)=C(d,i)*(d-i)/(i+1)
to compute each new value in constant time.

If we look at the bitwise complexity then we wind up paying a bit extra per stage for the combinations method (since it requires multiplication/division rather than just addition), but this only amounts to a (log d) factor. We're multiplying and dividing large numbers by small numbers (i.e. O(d) numbers), so no advanced multiplication techniques are involved. This extra O(log d) factor we pay is much smaller than the O(d) factor we save by only computing entries corresponding to our particular value of d.

Title: Re: Egg Drop: any solutions better than this?
Post by continuum on Sep 18^th, 2002, 7:07pm

Interesting. Given the number of eggs, "maximize the number of floors" is the dual problem of "minimize the number of drops". Mathematics is really elegant.

Title: Re: Egg Drop: any solutions better than this?
Post by Chronos on Sep 19^th, 2002, 11:48am

No, not given a number of eggs; given a number of eggs and of drops. If you have a given number of eggs but unlimited drops, you can still find the floor out of any number of floors: Just start at the bottom and go up one floor at a time.

Title: Re: Egg Drop: any solutions better than this?
Post by James Fingas on Sep 19^th, 2002, 11:56am

Yeah,

Mathematics may be beautiful but it is thorny. You can solve the problem three ways:

1) Given floors and drops, find eggs.
2) Given floors and eggs, find drops (as asked).
3) Given drops and eggs, find floors.

The easiest, #3, is the one we solved. To get from #3 to #2 is not necessarily easy, but we consider it doable at least. Once you have a good solution for #3, you can at least look up the solution for #2, even without finding it explicitly.

That's why we didn't bother to go back and solved #2.

Title: Re: Egg Drop: any solutions better than this?
Post by continuum on Sep 19^th, 2002, 4:44pm

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. :)

Title: Re: Egg Drop: any solutions better than this?
Post by BNC on Dec 26^th, 2002, 12:23am

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 :P:
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.

Title: Re: Egg Dropping
Post by jollytall on Oct 29^th, 2012, 12:35am

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.

Title: Re: Egg Dropping
Post by rmsgrey on Oct 29^th, 2012, 7:01am

on 10/29/12 at 00:35:16, jollytall wrote:

Do you have to descend to tell whether the egg splattered?

Title: Re: Egg Dropping
Post by jollytall on Oct 29^th, 2012, 9:11am

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.

Title: Re: Egg Dropping
Post by jollytall on Nov 11^th, 2012, 11:09am

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.

Title: Re: Egg Dropping
Post by antkor on Jan 3^rd, 2014, 5:44pm

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.

Title: Re: Egg Dropping
Post by Grimbal on Jan 3^rd, 2014, 11:10pm

Is it still with the restriction that you only have two eggs to break?

Title: Re: Egg Dropping
Post by antkor on Jan 4^th, 2014, 6:47am

on 01/03/14 at 23:10:37, 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. [hide]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![/hide]

Title: Re: Egg Dropping
Post by rloginunix on Jan 4^th, 2014, 10:31am

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 [hide]14[/hide].

And if you find my proof rigorous enough then it's not the average it's the optimal solution.

Title: Re: Egg Dropping
Post by Grimbal on Jan 4^th, 2014, 4:29pm

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.

Title: Re: Egg Dropping
Post by rloginunix on Jan 4^th, 2014, 6:44pm

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?

Title: Re: Egg Dropping
Post by Grimbal on Jan 5^th, 2014, 2:30am

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

Title: Re: Egg Dropping
Post by rloginunix on Jan 5^th, 2014, 11:04am

Got it.

Thanks, Grimbal.

Title: Re: Egg Dropping
Post by rloginunix on Jan 5^th, 2014, 12:01pm

I think I'm on to something. Check out this pattern.

[hide]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.
[/hide]

Title: Re: Egg Dropping
Post by rloginunix on Jan 5^th, 2014, 12:57pm

I've built [hide]12[/hide] tables covering all 100 floors based on the worst case scenario testing scheme. The sum total of all the drops ran thus:
[hide]
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
[/hide]
But apparently that is not the lowest average possible.

Title: Re: Egg Dropping
Post by Grimbal on Jan 6^th, 2014, 5:51am

I get
[hide]1045/101 = 10.3465[/hide]

Title: Re: Egg Dropping
Post by rloginunix on Jan 6^th, 2014, 10:50am

My testing floors were [hide]14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99 and 100[/hide].

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 [hide]one[/hide] 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:
[hide]
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
[/hide]
The last [hide]two[/hide] floors for any bracket always take [hide]14[/hide] drops to test (except for [hide]100-th[/hide] floor). I didn't sum these numbers vertically but went "across" by observing that [hide]2*14[/hide] is always there for all [hide]11[/hide] drops. This is also true for [hide]13 and 12[/hide]. However, the rest of the numbers [hide]2 through 11[/hide] 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 [hide]1035/101 = 10.24752475[/hide].

I wonder where I've lost [hide]10[/hide] attempts?

Title: Re: Egg Dropping
Post by antkor on Jan 6^th, 2014, 1:43pm

on 01/06/14 at 10:50:52, rloginunix wrote:

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?

Title: Re: Egg Dropping
Post by rloginunix on Jan 6^th, 2014, 6:38pm

I have found the discrepancy by figuring out Grimbal's testing scheme: [hide]9,22, 34, 45, 55, 64, 72, 79, 85, 90, 94, 97, 99, 100[/hide].

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):
[hide]
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
[/hide]
The sum total for these numbers is [hide]1045[/hide].

The only difference I see is the number of steps: [hide]14[/hide] vs [hide]12[/hide]. But the basic idea is still the same. Grimbal simply shifted the entire ladder of the scheme I used [hide]down[/hide] by [hide]5[/hide] 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.

Title: Re: Egg Dropping
Post by Grimbal on Jan 7^th, 2014, 10:10am

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.

Title: Re: Egg Dropping
Post by rloginunix on Jan 7^th, 2014, 10:19am

Using the [hide]12[/hide]-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 [hide]14[/hide] 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:
[hide]
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
[/hide]
The sum total for all the drops is [hide]1035[/hide].

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 [hide]11[/hide] terms each of which is [hide]14[/hide] 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 [hide]11[/hide] and [hide]12[/hide].

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 [hide]13[/hide] and it didn't work out.

I also tried to get rid of double [hide]fourteens[/hide] in such a way that the number of brackets remains at [hide]12[/hide] changing the scheme at the very end: [hide] ..., 89, 93, 96, 98, 99, 100[/hide] but the sum total of all the drops remained [hide]1035[/hide].

Need to try something else.

(Edit: fixed a typo in the table, was 084 for the bracket 09, now 085)

Title: Re: Egg Dropping
Post by rloginunix on Jan 7^th, 2014, 10:22am

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.

Title: Re: Egg Dropping
Post by rloginunix on Jan 7^th, 2014, 2:05pm

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.

Title: Re: Egg Dropping
Post by Grimbal on Jan 7^th, 2014, 2:58pm

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.)

Title: Re: Egg Dropping
Post by rloginunix on Jan 7^th, 2014, 5:05pm

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.

Title: Re: Egg Dropping
Post by rloginunix on Jan 7^th, 2014, 5:42pm

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.

Title: Re: Egg Dropping
Post by Grimbal on Jan 8^th, 2014, 11:36am

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

Title: Re: Egg Dropping
Post by rloginunix on Jan 8^th, 2014, 12:24pm

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".)

Title: Re: Egg Dropping
Post by Grimbal on Jan 9^th, 2014, 2:51pm

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.

Title: Re: Egg Dropping
Post by rloginunix on Jan 10^th, 2014, 8:42am

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.

Title: Re: Egg Dropping
Post by rloginunix on Jan 10^th, 2014, 11:16am

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.)

Title: Re: Egg Dropping
Post by antkor on Jan 11^th, 2014, 6:27pm

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.

Title: Re: Egg Dropping
Post by rloginunix on Jan 11^th, 2014, 9:04pm

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.

Title: Re: Egg Dropping
Post by antkor on Jan 13^th, 2014, 6:32am

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.

Title: Re: Egg Dropping
Post by rloginunix on Jan 13^th, 2014, 7:48pm

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]

Title: Re: Egg Dropping
Post by rloginunix on Jan 13^th, 2014, 7:52pm

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.

Title: Re: Egg Dropping
Post by rloginunix on Jan 13^th, 2014, 7:56pm

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

Title: Re: Egg Dropping
Post by rloginunix on Jan 13^th, 2014, 7:59pm

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.

Title: Re: Egg Dropping
Post by rloginunix on Jan 14^th, 2014, 8:38pm

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.

Title: Re: Egg Dropping
Post by rloginunix on Jan 14^th, 2014, 8:41pm

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.)

Title: Re: Egg Dropping
Post by Grimbal on Jan 16^th, 2014, 3:04pm

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.

Title: Re: Egg Dropping
Post by rloginunix on Jan 17^th, 2014, 8:33am

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.

Title: Re: Egg Dropping
Post by Grimbal on Jan 17^th, 2014, 2:20pm

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(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.

Title: Re: Egg Dropping
Post by rloginunix on Jan 18^th, 2014, 11:37am

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".)

Title: Re: Egg Dropping
Post by rmsgrey on Jan 21^st, 2014, 7:38am

on 01/17/14 at 14:20:51, 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(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 + min_k=1,2,...,f{d(k-1,e-1) + d(f-k,e)}

Title: Re: Egg Dropping
Post by Grimbal on Jan 21^st, 2014, 9:16am

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.

Title: Re: Egg Dropping
Post by rloginunix on Jan 21^st, 2014, 11:01am

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.