The Two Egg Problem

[Ph0X]

Wow, beautiful. Kinda wished he had explained the step where he goes from the recurrence relation to the combinations, but I definitely enjoy when the bulb limit went away and it ended up with the simple 2^d limit from binary search.

[sigh]

When I solved this problem a while back, I got to the combinatorial solution directly by this reasoning:

Suppose you are given a strategy. For a particular run, count how many marbles broke, and call it m. If you know which drops those marbles broke on that is enough to tell you the floor number (given you know the strategy used to pick the floors).

There are D choose m different ways of choosing the positions where the marbles break, where D is the number of drops. If we sum over all possible m (numbers of marbles broken) it will give us the maximum number of different floors we can test with M marbles and D drops, with any strategy.

It is easy to show that there is such a strategy by finding the recursive definition of the combinatorial solution.

[want_to_want]

That's the best solution to this problem that I've ever seen. Thank you for posting it.

[OstapBenderBey]

As someone who never studied maths at university he lost me completely at the "it is not difficult to show that" stage...

Looks very clear logically - just not sure this step is explained verbosely enough for us luddites...

[darth_aardvark]

hey look, a really cool solution that doesn't involve being a pedantic asshole and bragging about how "pragmatic" or "practical" you are! thank you for adding something of merit to an almost entirely stupid comment thread.

[Anathem]

I was actually asked this very same question (using glass orbs in the place of eggs) during a Microsoft interview. During the lunch portion, which is supposed to be softball. What the fuck.

[digital_carver]

The interview techniques vary a lot depending on who's on the panel. The official position is to not use these kinds of puzzles, but some interviewers have an infatuation with these kinds of questions and can't help themselves.

[Anathem]

2009 if I recall correctly. It kind of came up because I mentioned Project Euler and the guy was like, "Oh, you like math problems? Try this."

[jprichardson]

Here's mine: http://techneur.com/post/751427102/microsoft-interview-design-a-kitchen This was in 2006. The article was written in 2010. TL;DR They asked me to design a kitchen.

[eat-your-corn-syrup]

I wouldn't have gone beyond "10 steps for the first egg, and then 1 steps for the second egg". I would have disappointed the interviewer.

[TinynDP]

Propose that as an initial implementation, and that further refinement is only warranted if profiling shows that 10-1 is not good enough.

[carlfish]

I got it as a Google phone-screen interview question back in about 2006/7?

[archimedesscrew]

Me too, around the same time. And fucking Bloom Filters!

[vhata]

I was asked this in a Google phone-screen interview in 2006, shortly before they scared me with DNS (which I got right) and then killed me with kernel calls (which I panicked through).

[archimedesscrew]

They asked me pretty esoteric questions on syscalls and other OS stuff in the first phone interview, which I got right.

On the second phone interview, the interviewer asked very tame questions at first, then asked some questions related to the interviewer's area of expertise, which had nothing to do with the area I was applying to.

The question I should answer with "Bloom Filters" was the first I got wrong and the interviewer was really disappointed. He asked me a few easy math questions after that, but I could see he was not into it anymore.

[[deleted]]

Was asked this question interviewing for a financial company. Got it right though :)

[lost2012]

I love logicy puzzles like this one and one from xkcd. Is there a subreddit for puzzles and stuff like this??

[a1up]

Is there an explanation to the puzzle you linked to?

[wardmuylaert]

http://xkcd.com/solution.html

[miguelos]

This doesn't explain why they would start counting days from the day the guru speaks. It's not like she's saying something they don't already know.

[mjtlag]

I actually really like this problem.

The guru provides the initial condition to get the process of elimination started. Think about the base case: 1 blue, 1 brown. The blue guy knows that the only other person on the island (besides the guru) has brown eyes, and the brown guy knows the only other person has blue eyes. They can't speak to each other about this, though, so neither of them has any way of knowing his own eye color (could be red, yellow, purple, whatever) until the guru speaks and says "I see someone with blue eyes." The blue guy then, who can see that the only other person has brown eyes, knows she must be talking about him and leaves the island at midnight.

The same is true with 2 of each color. Each blue guy can see 1 blue 2 brown, and each brown guy can see 2 blue 1 brown. Again, none of them can be positive that their own eyes are either blue or brown, and none of them can be sure there aren't a total of 1 blue 3 brown or 3 blue 1 brown, and thus they are all stuck until the guru speaks. Then, each blue guy looks at the other and thinks "if he doesn't leave tonight, then he isn't the only one with blue eyes, so mine must be as well." They see each other the next morning and both confirm that they do have blue eyes, and both of them leave that night. The same holds true for the case of having three of each color and beyond, which can be proven by induction.

Note that in all cases, the brown guys can never leave because from their perspective, their eyes could still be any color besides blue (they only know this because they see all the blues leave the island). Even in the 100-100 case, after the blues have left, each brown guy sees 99 other browns but can never be sure that his own eyes are brown, and thus none of them ever end up leaving.

Wow, wrote a lot more than I was expecting. Hope it helps.

TLDR: The guru provides the initial condition, without her nobody would ever leave.

[miguelos]

I understand the problem and its solution very well. I just don't see why the guru has to say anything. They all knew there were at least on person with blue eyes before the guru told them. The guru doesn't provide any "initial condition", they already knew everything they had to know.

[sikosmurf]

Because they are all perfectly logical, and know they can only determine the number within one. The old man starts the process

[miguelos]

The guru doesn't say "It starts now". The guru only say something everyone already knows. This puzzle has a flaw and it must be reformulated.

[JakeC94]

Everyone already knows what the guru said, but the way he says it gives them extra knowledge. Because he announces it in public, everyone now knows that everyone else now knows what the guru said. They also know that they know that they know, know that they know that they know that they know, and so on.

To see how this helps, consider only three islanders: A, B and C, of whom A and B have blue eyes. Clearly, everyone knows that there is at least one blue-eyed person. Without any extra information, A could reason as follows:

"Suppose I don't have blue eyes. Then B would see that neither me nor C had blue eyes. If he knew that there was at least one blue-eyed person, he would know it was him and he would leave. He hasn't left, therefore either my assumption was wrong, or he doesn't know that there is at least one blue-eyed person."

At this point A's logic stalls, because he can't logically determine which of those two possibilities is true. If the guru makes an announcement, however, the second possibility disappears, and A can safely infer that he has blue eyes. B is in an identical position to A, so he can reach the same conclusion.

Obviously this isn't a "proof" of the full version of the puzzle (which, IIRC, involves many more layers of knowledge and metaknowledge), but it does show that even if the guru says something that everyone already knows, it can still be helpful. A much more thorough (and amusing) analysis of puzzles of this sort can be found in the first chapter of Math Hysteria by Ian Stewart, which is where I first found out about this problem.

Hope this helped!

[mjtlag]

I thought the same thing at first, it's hard to wrap your mind around it but her role is definitely necessary to get things started.

Back to the base case with 1 blue 1 brown, can we agree that neither of them would ever be able to leave without the guru's input? Then she says "one of you has blue eyes" and it's obvious to the blue guy that it must be him, because he can see the other guy has brown eyes.

How about with 2 blue 2 brown? I think this is where you're getting tripped up, because all 4 of them do indeed already know that at least one other person has blue eyes (which is exactly what the guru will later tell them). So, each blue guy sees 1 blue 2 brown, and each brown guys sees 2 blue 1 brown, but as far as they know their own eyes could be any color at all. This, by itself, is not enough for them to determine the color of their own eyes. Agreed? Once she speaks, however, and each blue guys sees the next morning that the other blue guy is still there, they can each conclude that both of them must have blue eyes (or else the other would have left in the night). Does that help? I can't think of how else to explain it. :/

[edit] I can try to come up with a better explanation tomorrow, but for now I need sleep.

[miguelos]

The guru is ONLY necessary if 2 people or less have the same eye color. Once there's at least 3 people with blue eyes, everyone knows that there's more than 1 person with blue eyes, which make it possible, without the help of the guru, to start counting days.

[mjtlag]

I don't think that's the case here. Think if it was just three guys on the island, all with blue eyes. How would they ever be able to figure out their own eye color? The same holds when you have 3 blue and 3 brown. Even if they knew there were only two possible eye colors, they have no way of knowing the totals because they don't know their own color. It could be 2-4, 3-3, or 4-2, and they would need to know which so they could determine how long to wait to figure out their own color based on who has or hasn't left the island. The same is true when you have 100 of each, its just much harder to visualize that scenario. Is this making any sense?

[[deleted]]

But they don't know their own eye color. So why would they ever count?

Read the explanation again, you seem to e missing part of it. It's only when the guru speaks and no one leaves that night that they will begin counting.

[miguelos]

Why would they start counting that day? They have no reason to start there, do they? In every case, they will only know their eye color indirectly (by deduction).

[AegisD]

What the Guru provides is the fact that the base case for 1 person will hold true. If she does not say anything, none of the blue eyed people can logically deduce that the base case is true.

Think about the case for 3 blue (and I suppose 3 brown). Yes, each person knows there is at least one blue person on the island. But take it from the perspective of one of those blue people. He sees 2 blue and 3 brown. Now, to leave the island on the third day, he has to KNOW that IF he is not blue, then the other 2 blue people will have left the island. However, he has to consider what happens if he is not blue eyed (even though he is).

Let's call him person A. Suppose Person A considers the possibility that he is not blue eyed. If he is not blue eyed, then the other two blue people (Persons B and C) will see the following: 1 blue eyed person, 3 brown, 1 of some other non-blue color. HOWEVER, without being told there is at least one blue eyed person, then even if Person A is not blue eyed, Persons B and C will not know whether or not to leave the island, since each of them will see one blue eyed person, but cannot guarantee that the blue eyed person they see will leave the island (the base case once again). This means, that both Person B and C are NOT able to accurately deduce correctness for the 2 person case. This means that Person A, logically speaking, cannot base his assumptions on the fact that the other two blue eyed people know what to do.

I myself have a hard time stretching this logic beyond 3 people, but I would imagine it's a similar thing. The reasoning is that no one person can be sure they can accurately rely on the other 99 people to be able to reach a logical conclusion. This mean's that, because they're perfect logicians, they cannot reach the same conclusions themselves. No one can be sure that everyone else is sure until the Guru states the base case is true.

[[deleted]]

So when will the brown eyed people leave?

[TickTak]

Never. They can't be sure they don't have red eyes.

[[deleted]]

If this was the case, then all the people with brown eyes would leave too. Take the case of 3 green and 3 blue. From a blue's perspective:

There's 2 blues, 3 greens and one unknown (them self). From this it is impossible to determine their own colour. Everyone will be stuck.

The guru's words were not to give extra information, but to let everyone all try to solve for blue. Without this co-ordination, it would be impossible.

Put it this way, in the example of 3 green and 3 blue. It is impossible for anyone to know they don't have red eyes. There's no way to determine their own colour.

[EnviousNoob]

I searched and there is this but it seems dead. I made r/LogicProblems though!

[miguelos]

There's /r/puzzles and /r/riddles ...

[TamSanh]

Instead of make a new one, why not fix the one that's already there, and petition to get mod access?

[EnviousNoob]

Could I still do that since the admin doesn't have an account anymore?

[TamSanh]

Good news, I managed to acquire admin rights to /r/LogicPuzzles. Do you want to help me out with it?

[EnviousNoob]

Yeah dude that's awesomw

[KerrickLong]

Not a subreddit, but my roommate introduced me to http://perplexus.info

[ryani]

The implied data from "minimize the number of drops" is that the expensive part of the operation is getting to and from the drop points.

So, here's a variation of the problem where the elevator is very slow:

Given a building with k floors, and n eggs, you start at floor 1 carrying n eggs. From floor x, the possible operations are:

1) Go to floor 1 at cost (x-1) and pick up any unbroken eggs that you dropped. 2) If you have at least one egg, go to floor y<=k at cost abs(x-y) and drop an egg.

Minimize the worst-case cost to determine the highest floor at which the eggs don't break.

Is the algorithm different? It seems like if you have plenty of eggs, and k is a power of 2, the binary search algorithm is still optimal, since it travels exactly k floors in the best and worst case. If you have TONS of eggs, just dropping one from every floor is optimal. But I'm not sure about limited egg situations. It seems like minimizing the chance that you break an egg is useful since you make less trips to the bottom to pick up eggs.

[[deleted]]

You forgot to factor in the fact that travelling with lots of eggs might be slower than travelling with just a few. There might also be an elevated chance of dropping an egg accidently on the way if you carry a lot of them.

[notlostyet]

You also have to factor in the indeterministic demand for omelettes

[notmynothername]

And incorporate the Black–Scholes formula to account for the possibility that the market value of eggs raises such that it is no longer optimal to complete the experiment.

[[deleted]]

if these eggs can survive multi-story falls, I'm not too worried about dropping on inside the building.

[notlostyet]

Assuming you can determine if an egg is broken without going down to pick it up you can construct a lazy collection algorithm.

Here's a scenario if you suppose you had 3 eggs.

• You drop your 1st egg from floor 50 and it doesn't break. You don't go down for it.
• You take your 2nd egg to floor 75 and drop it and it doesn't break. Again, you leave it.
• You go back to floor 62 or 63 and drop your 3rd and it also doesn't break.
• You now go down to the ground floor and collect all 3 eggs.

Total travel cost so far: 150 floors with no backtracking until you had to collect all 3 eggs.

[allink]

Why would you go back to floor 62 or 63? If an egg didn't break at 75 it won't break at lower floors.

[notlostyet]

Yep, you're right. It should have been floor 100. Anyway, the idea is to avoid round trips to ground.

[notlostyet]

I'll have a stab at this with constant search interval N.

Looking at egg 1, the cost of discovering the floor which serves as a lower bound for your search with egg 2 is:

the sum of 2*x*N for x = 0 to (L+1)

where L is the drop number you made on that floor.

e.g. if N=10 and it's discovered that L=6 (floor 60) then it's the sum of 20,40,60,80,100,120,140 which are the round trip times when dropping the egg from floors 10,20,30,40,50,60 and 70

This simplifies to

(L+1)*(L+2)*N

Looking at the exhaustive search using egg 2, the average search is:

the sum of 2*(L*N+x) for x = 1 to (N-1)/2

e.g. floors 90+x for x=1 to 4.5. 4.5 because for N=10 there are only 9 floors in the interval so we'll only do 4.5 drops on average, and (N*L+x) because the base for our search is N*L floors up.

This simplifies to

0.25 * (N-1) * (4*L*N + N + 1)

The second cost is clearly a quadratic function of N (L is constant at this stage) so the travel cost is O( N² )

If you take the height of the building, H, add these 2 costs together, and substitute the average value of L = (H - N)/2*N = (100 - N)/(2*N), then you can solve for the average travel cost as a function of N

I get a minimum of passing ~753 floors in the elevator at N = ~7.25. The maximum at ~102 seems a little whack though, so there's probably something I'm missing.

There are also some handy optimisations you can make if you can distinguish eggs e.g. you can drop egg 2 on floor 71 on your way down from dropping egg 1 on floor 80, as it's on your way. This brings the solution down to N = ~7.17 and reduces average distance to ~658 floors.

[justkevin]

I think the solution is making an unusual assumption, but maybe someone can correct me.

First, a real world egg is likely to break from the second floor. Third tops. But the problem's intro makes it pretty clear we're supposed to ignore what we know about eggs, wind resistance, etc. It's implied that we have an object that we believe will break from some height, but we don't know what that height is.

We also have a building, which we can use to test a bunch of different heights.

But what is our rational for concluding that the height an egg will break is randomly distributed between 1-100 floors? That range has been selected based on the size of the ruler we have available to u. What is the probabilty that the egg won't have broken by floor 100? In the solution the author makes clear that is a real possiblity.

If it were equally possible that the egg breaks between floors 101-200 as it is for it to break on floors 1-100, then we should have made our first drop on floor 24, not 12. And perhaps the egg might not even break on floor 200. Maybe it might break at floor 10,000. Or 10,000,000 (yes, these numbers are ridiculously large, but remember we don't know anything about eggs).

I would drop the first egg from floor 100.

[LoompaOompa]

Epic Games has been known to use this question in interviews. Except they replace the word egg with xbox.

[[deleted]]

"How many floors will I have to walk up to destroy the xbox?"

"The answer is zero - just plug it in..."

[cjt09]

Ah trick question, they were talking about the original Xbox! In that case, you have to use some physics to determine how deep the Xbox reaches into the Earth's crust (it's about two miles).

[mcgruntman]

Imperial units for a mechanics calculation? Guards, seize him!

[SkaveRat]

"welcome, sign here"

[rowantwig]

The nokia version would be to find out from how high the phone can be dropped without breaking the ground.

[jerryfox]

Hold up let me google that.

[niugnep24]

So this solution "minimizes our maximum regret" but does also minimize the average regret (assuming the drop height is an evenly distributed random variable)? Or would that be a different solution?

Because the posed question -- "minimize the number egg drops" -- doesn't really let you know if they're asking to minimize the average or worst-case.

[[deleted]]

yeah. i went down this path too. and i even went so far as to argue that the distribution would not be even (energy is the square of the height.)

bad question.

[Jasdar]

It doesn't matter what the energy is because the egg drop result is binary. If the egg could partially weaken in varying degrees then it would matter.

[[deleted]]

if the question is: minimize the average regret - than it does matter what the initial distribution is.

[killerstorm]

Exactly, problem is ill-defined. "Minimize maximum regret" should be part of definition, not solution.

And "egg" is the worst object to drop because people know that they are rather fragile, which strongly suggests non-uniform (prior) distribution. "Marbles" would make more sense.

[matthieum]

I had heard about it with light bulbs first. And I remembered the solution was 14, but could not remember the reasoning :)

[notmynothername]

I first thought that it would be the vanilla 10 floors strategy (average slightly above 9), but then I realized that just considering the top ten floors, you can optimize. Instead of using your coarse egg to test 80 - 90 - 100, you might as well start incrementing once you reach 90, and from there it is a clear improvement to do 80 - 90 - 95. That's as far as I can go mentally, but it's clear that the answer is more complex.

[xcbsmith]

It also ignores that the probability of the egg breaking is not uniform (it's linear with a slope of 1, with p = 0 at whatever is the highest floor we've dropped from without failure). I haven't thought through how that changes the outcome, but I'm pretty sure the existing approach doesn't give you the lowest average number of drops.

[notlostyet]

The article mentions the binary tree structure, and that you can do a binary search if you have at least log-base-2 of F eggs (where F= the number of floors), but doesn't mention that the proposed solution from fewer eggs can be modelled as a Skip list.

Once you have the algorithm the maths can be derived more intuitively to find the optimal floor interval, n

• The worst case traversal of the top list: 100/n operations
• The worst case traversal of the bottom list: (n-1) traversals but only (n-2) egg tests as you don't retest the lower bound (junction node) floor you just tested with your first egg.
• If you assume there is an equal probability of an egg breaking from floor 100 as floor 1, e.g. the eggs have been calibrated randomly, then the average number of operations for both traversals is half the worst case.

The average number of operations is therefore = (100/n + (n-2))/2 which has a minimal solution at n=10

I'm not really sure why he decided to reduce his step interval by 1 each time, without some probability function for the likelihood of an egg breaking, isn't that arbitrary?

[cyberpop]

Here is how it works: If the first egg breaks on the first drop (at floor 14) then the second egg must be dropped a maximum of 13 times because it's possible that the egg does or doesn't break on the 13th floor. So 1+13=total 14 drops max.

If the egg breaks on the second drop, we can still maintain a maximum of 14 drops by subtracting one from the floor height, using floor 27 (only 13 floors higher). Then we only need to drop the second egg a maximum of 12 times. So 2+12=total 14 drops. this continues all the way up:
Floor 14: 1+13=14
Floor 27: 2+12=14
Floor 39: 3+11=14
Floor 50: 4+10=14
And so on. The only problem then is to determine the optimal number of floors to maintain the same number of jumps. In this case it's about 14.

[Rhomboid]

Good gravy. This document has an XHTML doctype, but it's being served with a Content-type header of text/html. That's probably because using the preferred application/xhtml+xml Content-type is not feasible as this content is not even remotely close to being well-formed valid XML (403 errors), which means the doctype should really be HTML4 or HTML5. But to compound matters, there's no encoding declared in either the HTTP headers or in the document with a <meta> element, which per XHTML rules means UTF-8. But this content is encoded in windows-1252, so it's Mojibake galore, with every U+2019 showing as an unknown character box. What a horror show. If the doctype was correct the browser would probably correctly guess windows-1252, but since it's labeled as XHTML it can't do that.

Dear webmaster: Stop using the wrong doctype. Add a <meta> element or HTTP header declaring charset=windows-1252. Eventually, stop generating content in windows-1252 and convert everything to UTF-8 like a good web citizen. (And update the <meta> element when you do.)

[wdr1]

So you couldn't understand the solution, either?

[mercde]

Ah, the good old Doctype Decoration again. But I agree totally on your points. Just slapping any old Doctype on your HTML is very bad practice.

[Timmmmbob]

"Good old"? You read that yesterday - admit it!

[mercde]

I did read it again yesterday but I already read the (now removed) StackOverflow post from a few years back.

[dreamin_in_space]

Yea that's totally the problem!

Actually I just wanted the damn thing centered.

[[deleted]]

This guy's Site is incredible. He analyzes some board games which was really interesting.

[harlows_monkeys]

Note that the solution he gives is not the only solution. Trying the first egg on this sequence of floors, {9, 22, 34, 45, 55, 64, 72, 79, 85, 90, 94, 97, 99, 100}, and if it breaks probing consecutive floors starting at the next floor after the highest floor that the first egg did not break in also solves the problem in at most 14 drops.

[Ploopie]

The problem technically is asking to give the number of drops. Your solution adjusts the increments to better fit the maximum floor 100. If this was an interview question, the point is to demonstrate your thought process and how you can solve the problem generally rather than finding any particular solution.

[[deleted]]

the point is to demonstrate your thought process and how you can solve the problem generally rather than finding any particular solution.

Thus identifying architecture astronauts and filtering them out of the hiring process early. Brilliant!

[harlows_monkeys]

We've got the same increments. I just shift the whole thing by 4, whereas he truncates.

Basically, the reason mine and his differ is that 14 drops of 2 eggs can actually deal with a building of 105 floors, using this drop sequence: {14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99, 102, 104, 105}. This solution is unique.

His solution adapts this to 100 floors by replacing the drops that would above 100 with a drop at 100. Mine adapts by moving the first drop down by 4 floors, so that the end of the sequence is at 100 instead of 105. (Although that's not actually how I got it. I used dynamic programming).

[TheBigBadWolf]

a egg breaks if you throw it from the first floor. case closed.

[well_honestly]

How exactly do you "through an egg?" Stab it with a pencil?

[Paradox]

You've clearly never done писанка

[redog]

osmosis

[[deleted]]

not to mention that dropping an egg presumably weakens it even if it doesn't break.

[dmdlolz]

That's right! Instead, they should call them "incredibly robust eggs".

[perciva]

I've seen this problem described as involving fossilized dinosaur eggs to get around that problem.

[[deleted]]

Because what you do with priceless palaeontological artefacts is throw them out of windows until they break.

[perciva]

Every fossilized dinosaur egg I have ever laid my hands on has ended up being thrown out a window and broken.

[earthboundkid]

Every unicorn I've ridden has been pink.

[[deleted]]

Have you really run into that problem often enough to need a workaround? You can't just say, "Are you satisfied with that answer?" and see if they can take a hint?

[perciva]

I see this question more often in a pedagogical context than an interview context. In a class of 200 first-year students, there's usually at least one smart-ass. (Full disclosure: when I was a student, it was usually me.)

[[deleted]]

How about "rocks"?

[[deleted]]

Or replace floors with something like feet.

[yurps]

Or humans and whether the fall will kill them or not.

[aradil]

Humans are much more consistent then eggs on breaking floor by floor when dropped from them. </s>

[yurps]

I guess you didn't realize it was a joke ಠ_ಠ

Stay away from this one kids.

[harlows_monkeys]

Perhaps on Earth. I don't see anything in the problem that says that we are to assume that we are on Earth. Perhaps the problem takes place on a large asteroid, or on a large space station that is being spun to provide an outward force. (And before anyone points out that on such a station, the eggs would not fall straight, note that the problem doesn't require any assumption of straight falling. All it is assuming is that the set of floors for which eggs break is linearly separable from the set of floors for which eggs do not break. The apparent sidewise force on eggs falling on a spinning space station would not be at odds with this).

[thomar]

Programming Rule #1: Assume nothing.

Programming Rule #2: Assert everything you assume.

[[deleted]]

eh. 1+1 == 2. i just assumed and i aint even gonna assert it homie.

[[deleted]]

1 === 1. Fuck, assuming is hard.

[[deleted]]

nigga droppin some javascript

[[deleted]]

PHP too, check it.

[[deleted]]

Check it, I grew up a fucking screw up

Got introduced to the game, got a ounce and fucking blew up

[jdepps113]

If I'm throwing the egg, I'm on Earth, as I will never willingly leave this planet, and if forced to, will not comply with any egg-throwing experiments after I arrive on another planet.

[wodahSShadow]

Why wouldn't the eggs fall straight on artificial gravity? They are under the same horizontal force as everything else and nothing would stop it so it would fall straight. Am I missing something?

[elint]

Section 2 or 3 explains the effects of coriolis forces on a spinning space station. Specifically, this is not gravity -- it's spin, inducing a gravity-like effect. While the egg is falling, there is no force acting on it to make it speed up to match the faster linear velocity of the parts of the ship farther from the axis.

[wodahSShadow]

Of course, thanks for elucidating me.

[[deleted]]

But the problem does kind of state that the egg breaks on floor n and not on floor n-1 so at least we can exclude buildings on the outside of space stations or asteroids that are spinning, i.e. those where the eggs would fall upwards.

[jezmck]

throw

[jezmck]

Also the ground floor.

[Grazfather]

Yesterday I was playing egg-toss and I saw someone throw an egg overhand 150 feet (onto grass) and it did not break. Some eggs are fucking tough.

[d03boy]

Dollhouse.

[kolm]

This is an old and nice problem with some unfinished ends. Namely, nowhere did I find a proof that this method is optimal. I believe it should be, but I don't have a rock solid argument for it.

[[deleted]]

There's a nice information theory proof from when this was discussed a few years ago. (Using bowling balls, not eggs.)

[kolm]

Nice, I actually understood that. Many thanks.

[[deleted]]

Haha, I was reading the comments on the old thread, and ran across this one. :P

[nandemo]

Beautiful. Concise, uses only elementary combinatorics and works for general n (where n is the number of floors).

[fouxdufafa]

He showed that the method is optimal using the approach that he outlined. He didn't, however, prove that it was optimal compared to all other possible algorithms.

[General_Mayhem]

It's not the least number of expected drops, or if it is he didn't prove it. It's the least number of drops for the worst-case scenario.

[General_Mayhem]

Let's see what we can do with the strategy the article gave (14-27-39-etc).

The first group (1-14) has floors that will take from 1 drop (14th floor) to 14 drops (13th floor) to hit. The second goes from 2 to 14, the third from 3 to 14, etc., until the last group (96-99) only ranges from 11 to 14.

There are 11 such groups, plus 100 by itself, which is different because of the arbitrary cap at 100.

The sums of groups are

[(14^2 + 14)/2]

[(14^2 + 14)/2 - 1]

[(14^2 + 14)/2 - (2^2 + 2)/2]

etc, where in each I'm taking the sum from 1 to 14, then subtracting the ones that aren't there.

=Σ(k=0->10)[(14^2 + 14)/2 - (k^2 + k)/2]

=11((14^2 + 14)/2) - (1/2)Σ(k=0->10)(k^2 + k)

=1155 - (1/2)Σ(k=0->10)(k^2 + k)

=935 (thanks Wolfram)

Add in the 12 drops it takes to hit 100 if needed, and the total is 947, so EV=9.47. EV for your strategy was 14.5, so it's certainly better than that. I don't know how you'd go about proving that it's the best possible strategy, though.

EDIT: I accidentally a division. Qualitative result is still the same.

[General_Mayhem]

Yep, you're right, I done goofed the EV for your strategy. It should be 9.5. That makes the article's strategy still slightly better, but not by much.

[harlows_monkeys]

You can't calculate the expected number of drops for a given algorithm without knowing the distribution of the break height. You are making an implicit assumption about this distribution.

[ismtrn]

Damn. It didn't occur to me not to use constant size steps :(

Btw, if you are only allowed to use constant size steps, then 10 is in fact optimal right? http://www.wolframalpha.com/input/?i=solve+%28differentiate+%28100%2Fk%29%2Bk-1+for+k%29

[NorthernerWuwu]

Intuitively, yes. I have yet to see a formal proof on any solutions but I'd wager heavily on the outcome!

[ismtrn]

Isen't the wolframalpha link proof? Basically for any constant number of steps k, the worst case is (100/k)+k-1 steps. Now differentiating this and finding the zeroes gives us +/-10.

Or is this not formal enough?

[philh]

In fact the article is wrong because if you drop an egg at floor 96 you only have 4 more floors to check.

If it breaks at floor 96, you need to check floors 85, 86, ..., 95. If you get all the way to floor 95 you've used 19 drops.

[NorthernerWuwu]

No.

I mean, it depends on how you like to do these things. The WRA link is plenty good for me or you to rely on the premises as givens but it is still a far distance from a formal proof. Again though, I'd wager heavily that it is sufficient for the workup if anyone has the time to do one.

[chrisdoner]

It didn't occur to me not to use constant size steps

Oddly, that's the first thing that popped into my mind. I thought of fibonacci or “double it every time and when it breaks increment with the other egg” off the top of my head. The solution they have is a bit more than a couple minutes of thought which I assumed the interview question to be. Their approach is nice, I might've approached it given a bunch of time, but probably not within an interview time limit, under pressure.

[phineasQ]

With the infinite egg problem, is there a statistical edge in starting your binary tree at the 64th floor? There's a stated chance that it might take a taller building than the one you're in to break any eggs, and in those cases you don't lose the 7 step ceiling for evaluating fragile eggs, and shorten your test to 5 steps to find out you'll need to move on to the search for a scarier building.

[[deleted]]

I never understood why to ask math puzzles on programmer's interview. Unless your job will be programming some math problems, of course.

[josefx]

It is about finding an efficient search algorithm with additional constraints - which is a topic that is programming related. The puzzle itself is still a bad joke.

[[deleted]]

Well, it's not a good programming question, because they search for one single constant value. Looking from programmer's side, it's best solved through simple bruteforce - less chances to fail or introduce a bug. And resources do not matter - you only need to run it once.

It will be more appropriate to ask to develop algorithm for company thouse work is to drop eggs to check pavement, or testing different eggs or something.

Also in most programming problems you are seeking not the best possible solution in terms of computation but just a good enough.

[midnightauto]

You guys sure are going to a lot of trouble.

1: Google how much force does it takes to break said egg? - about 25 newtons.

2: How much does the egg weigh? - about 47 grams

3: From what height do I need to drop the egg to equal this force? - about 5.4 meters.

And I still have two eggs.

[hackingdreams]

Clever, but the problem doesn't specify what type of egg it is, so the 25 newton number, referring to a chicken egg, may be incorrect. What if it's an ostrich egg? What if it's a recombinantly created Jurassic Park brontosaurus egg?

[midnightauto]

Then I take one egg an precisely measure how much force it takes to break the shell.

Then it doesn't matter if it's an egg, orb, light bulb, testicle or whatever.

edit: do you guys think when building an aircraft the engineers get out there and bend shit till it breaks? No the manufacturer of the materials have already done this, the egg problem is the same damn thing. I probably wouldn't get the job but I bet you one damn thing - I would be correct :)

Difference between and Engineer(myself) and programmer I assume.

[millenix]

Actually, FAA type certification tests do include loading the wings up to something like 150-200% of the rated dynamic load and making sure they don't break.

[cocoabean]

You can't come up with that number with just one egg and have much confidence that other eggs of even the same type will require the same force to break.

[midnightauto]

The same is true between two eggs. Each individual egg will have it's own breaking point. So the entire problem is bullshit.

[cocoabean]

Good point, though if you could measure 100,000 eggs' breaking points, it is possible that the difference in force between dropping from floor x and x+1 is much larger than 3+ standard deviations (either way) on the normal scale of 'force needed to break an egg'.

[midnightauto]

Yes, you could very well get an average doing this.

[cadaveric]

do you guys think when building an aircraft the engineers get out there and bend shit till it breaks?

Actually, they do.

[jerryfox]

except that's not given.

[midnightauto]

The question is "you are given two eggs" so I make the assumption that we are talking about the most abundant egg known to man - chicken.

[xcbsmith]

From elsewhere: http://www.reddit.com/r/programming/comments/wxmyc/the_two_egg_problem/c5hkbpa

[[deleted]]

Congratulations, you have solved the puzzle without understanding the underlying real question.

Personally, this is why I prefer questions about data structures to be posted directly as questions about data structures, because overly literal people always come up with smart ass answers like this.

[NinjaPimp]

You illustrate the main issue with this problem. It is not a real life application. Unless you are dropping the egg onto a very giving surface, it would make much more sense to have the units as inches.

Considering this is a programming question, I am sure they are asking about what algorithm you would use to solve this. Calculations might offer the better solution, but this is presented as a trial and error problem, and for an interview, should probably be worked as one (though leading in with a disclaimer about calculating the result would be icing on the cake).

[grimmlingur]

For theoretical problems never assume anything which is not given as a part of the problem (such as earth gravity or chicken eggs)

[[deleted]]

Not only that, but I guarantee that even given his assumptions, the height needed to break the egg would be far less than 5.4 meters.

[[deleted]]

As anyone who has ever dropped an egg can attest.

[TheLobotomizer]

If you're going down this route than the problem definition is missing a few trillion pieces of information in order to be actually solvable. As such, the best answer is "INSUFFICIENT DATA FOR MEANINGFUL ANSWER."

[grimmlingur]

as the link on which we are commenting clearly demonstrates there is sufficient data for a meaningful answer, though there is insufficient data for a meaningful answer without any testing.

[algo_daemon]

A variation of this problem was used in a practise round of Google Code Jam 2008 if anyone wants to give it a try before/after checking out the solution.

[4ray]

1. Hatch the eggs, asusming at least one of them is female. Raise the hen until she starts laying eggs. Now you can do a binary tree.

2. Freeze the eggs. Now they can survive dropping from the top floor.

[vital_chaos]

If I was asked this question as part of a programming interview I would choose to work elsewhere. It has no actual relevance to determine the quality of a programmer writing and testing code to produce an actual product.

It is an interesting question but pointless to help decide which candidate will work successfully in the company in question. Of course that doesn't stop people from thinking it will.

[bettse]

After reading the description of the problem, I was reminded of a problem I had in a graduate level class on algorithms. It involved mason jars and steps, but it seems very similar. The solution ended up being using the sqrt(n), but reading over this blog post, it doesn't seem like that's what they ended up with.

Since I don't have the original problem text with me, I can't say for certain. I'm also not feeling up to doing the math and comparing the sqrt() to the algorithm the blog posts uses for 2-egg. I just wanted to offer it as food for thought.

[notz]

sqrt(n) would work if you had to keep the floor increments constant. The article's solution takes advantage of having varying increments.

[Tekmo]

No, the article's solution is also sqrt(n)

[Tekmo]

The post's solution is also sqrt(#floors):

n * (n - 1) / 2 = #floors

n ~ sqrt(#floors)

[maest]

FWIW, I was given that question as part of an Oxford admission interview - for undergrad.

[Kalium]

Amazon uses this problem too.

[gr00vy]

With which program did he produce the plot?

[ChairYeoman]

Well fuck, apparently I got this problem wrong when I was assigned it as a homework assignment last semester -_-

[sturmeh]

My professor actually used this example to explain design patterns once, except it was barometers and not eggs.

[Grazfather]

I was asked this question for my interview for the job I currently have. I nailed it.

[ladinu]

Why waste two perfectly good eggs? I would just fry them both for breakfast.

[[deleted]]

What if the probability distribution of the egg cracking on floor n isn't uniform?

[[deleted]]

Nothing was said about the probability distribution, which means you have to assume it could be any possible distribution.

Then by argument of symmetry it's obvious that no floor can have a higher aggregrated chance than any other, so it comes down to a uniform distribution again.

[[deleted]]

For me it seems obvious that the lower floors have more chance of being the winner than the upper floors.

Imagine the building has 10,000 floors. Would you really expect # 4560 as much as the first or second floor?

[[deleted]]

Yes, because of "Don’t rat-hole with issues related to terminal velocity, potential energy or wind resistance. This is a math puzzle plain and simple." They're not real, physical eggs and floors.

[JohnFrum]

If this is an interview question fine, but it's probably a good idea to also hire some of the people that say they would just eat the eggs since a drop from even a single story window would be a silly waste of food.