The Two Egg Problem | Hacker News Reader

The Two Egg Problem

datagenetics.com

217 pointsslig81 comments

An issue with this puzzle is that the objective is not clearly stated upfront. The author should make it clear from the outset that the goal is to minimize the number of drops in the worst case, rather than to minimize the average case, especially since optimizing the average case is (in my experience) more common in optimization problems. He asks in parentheses what the worst case is, but that just sounds like a side question:

> The question is: What strategy should you adopt to minimize the number egg drops it takes to find the solution? (And what is the worst case for the number of drops it will take?)

Then in the solution he says:

> Problems where the solution lays lower down the building are taking less drops than when the solution lays higher up. We need to come up with a strategy that makes things more uniform.

It is not explained why it has to be more uniform.

A more minor issue with this puzzle is that for the sake of thoroughness, the author should say is that the number of floors required to break the egg follows a uniform distribution (i.e., every floor is an equally likely candidate).

optimizing the average case is (in my experience) more common in optimization problems ... the author should say is that the number of floors required to break the egg follows a uniform distribution

Then again, optimizing the worst case performance can be done without worrying about the underlying, and unknown, distribution of the lowest egg breaking drop.

If we start optimizing the average performance, then we need to assume something about the distribution (is it uniform? exponential? is there a bump in the middle?), and different distribution will have different optimal search strategies.

Looking at the worst case keeps the problem algorithmic, the version you propose would be more an exercise in probability calculus.

That may be true. Lunchbox's point holds true regardless: the problem statement is ambiguous, and is easy to correct so that it is not so.

Well, the standard in computer science is to optimize algorithms and discuss their performance for the worst case, so if we assume he's talking from a CS perspective, I find it natural to assume he's talking about that. There are a few exceptions, like QuickSort, but if some tells me to optimize some algorithm, I'll assume he's asking for optimization of the worst case unless he says otherwise or it's clear that the worse case is much rarer than some other case (I'd ask if I think that).

These considerations certainly exist in every day code as well. If you change the daily reporting process to have a worst case run time of 25 hours then you lose, even if the mean run time is cut in half.

> The author should make it clear from the outset that the goal is to minimize the number of drops in the worst case, rather than to minimize the average case

If the probability of an egg breaking on any particular floor is uniform over all floors--something reasonable to assume unless you're told otherwise--the average case is the worst case.

No. The worse case is when the topmost floor is the most likely to break the egg. And it's not reasonable to to assume anything about the distribution, so there's not a "most reasonable" case. Except maybe assuming that the higher the floor, the higher the chance of breaking the egg, simply because we are talking about things breaking and height plays a factor in that.

EDIT: actually, the worse case depends on the algorithm you are using; if you are using linear search, the worst case is when the egg won't break for any height. So yeah, in that case the distribution is uniform. But it seems like grasping at straws.

> An issue with this puzzle is that the objective is not clearly stated upfront. The author should make it clear ...

It's an interview question. You're supposed to ask for clarification. In fact, demonstrating your ability to elicit requirements is an important part of a technical interview.

That doesn't make any sense for a webpage. You either state the problem cleanly, or you explicitly discuss the point of clarification interview questions. But just putting up an ambiguous question with no recourse for the reader (other than carefully reading the answer and inferring what the author meant to ask) is sloppy.

> The author should make it clear from the outset that the goal is to minimize the number of drops in the worst case, rather than to minimize the average case [...] A more minor issue with this puzzle is that for the sake of thoroughness, the author should say is that the number of floors required to break the egg follows a uniform distribution (i.e., every floor is an equally likely candidate).

These two are incompatible. Once you state you are interested in worst case, stating that the number of floors follows a uniform distribution is irrevelant, and IMO confusing; the only relevant thing is that every floor is a possible candidate.

Let's say an egg costs 1 egg (1E). This means that for management to give us 2 eggs, they were willing to spend 1 additional egg to let us make (in the worst-case) 14 trips vs 100 if we only had 1 egg. So 1 egg < 86 trips in labor cost.

But they weren't willing to give us a 3rd egg. This means that 1E is more than 5 trips. So our labor cost is less than E0.20/trip (assuming a uniform labor cost per trip), but more than E0.012/trip (E1 / 86 trips).

My goal is to find someone willing to work for E1 for 100 trips. This would be be between 1/20 and 86% of my salary (management's choice don't give me enough information to know exactly how much I will be making in eggs).

So if I can find someone* willing to work for that labor cost, I can give him the 1 egg problem, and I can give him the other egg to pay his salary, I then I can spend my time doing something more interesting while still achieving management's objectives.

*Assume the cost of finding an employee is zero. This is an important assumption to make in an interview.

This could've been something much mor expensive and dangerous to use - for example atomic bomb test to check at what elevation when detonated it would affect the ground (just making this up, btw)

I was asked this question at a Google interview in 2006. At that time I worked it out mathematically as the author has here. Only afterwards did I realize that it is a simple Dynamic Programming problem.

Let f(y) be the number of drops required with y floors remaining. At a drop from floor x, either the egg breaks and you must test all floors from 1 to x-1, or else the egg does not break and you have reduced to a smaller sub-problem with y-x floors. So the number of drops required is 1 (for the current drop) plus the max of either x-1 or f(y-x). We simply minimize this value over all potential floors x from 1 to y.

Here is a solution in C++: https://gist.github.com/3156157

This is really helpful ,thank you for the example. Does anyone know of any other resources for simple Dynamic Programming examples?

I found the concise explanations here very helpful: http://people.csail.mit.edu/bdean/6.046/dp/

The blog author is very smart.

However, he is not very clever.

From my experience in the real world, I know that an unprotected egg will smash when dropped from one story, guaranteed. No need to go up 14 or 27 or even two stories.

(I also know that it is possible to devise protective enclosures to keep an egg from breaking when dropped from 6 stories. The Society of Women Engineers often sponsors competitions. Been there, got the T-shirt.)

Yeah. I dropped an egg from the kitchen counter and it broke. Ergo, first floor it would break.

Except of course, the article doesn't mention what the landing surface is, or whether it is what we think of as an egg, or some hypothetical super-egg. This would seem to be discounted by the "There are no tricks, gotchas or other devious ruses" clause, however. If the point of the article is to make it purely a mathematical problem, then pretty much anything except an egg would work, like "A strong box".

Otherwise, it's pretty much a "work out this problem but automatically disregard anything that I don't think should be part of the solution" interview question, that whilst I have no doubt are asked by many middle manager interviewers, would imagine is a little below microsoft or google.

All it would take to remove the real-world problem would be to change the object from an egg to a ball made of a material of unknown strength and toughness.

Poor specifications lie at the root of many a programming problem.

It's a fake egg made up of a material of unknown strength and toughness. Alternatively, it is made up of the brain of a thousand people who find irrelevant questions about logic puzzles - they are made of similar material!

Yes but this isn't a programming problem. It's a math thought experiment.

The real thing I'm wondering is why are you making a big deal about this? You obviously have the mental capacity to come up with the concept that it's a special material, why can't you just pretend that's what it is and not make a big pedantic joke about it? What is added to this discussion by pointing out something we all know - that eggs break when you drop them from shoulder height.

I hear you on that, and it can be annoying when people knowingly pretend not to know what you are talking about. However, the most groundbreaking things are often not so much the discovery of clever solutions as the recognition of what the actual problem is. In my work creating custom workflow apps, discovering the question is by far the most difficult part.

I think it's a fun problem and the main reason I wouldn't ask it is that it's probably on the banned interview questions list by now (for being too well-known).

An interview isn't a written exam. You don't lose points for bringing up real-world considerations - quite the contrary! But the interviewer might ask you to solve the math problem anyway (perhaps by modifying the question a bit, on the fly).

No, I think this is a great way to discern reasonable from unreasonable people. Unreasonable people would miss the question entirely and bring up these issues. Reasonable people would quickly disregard such jibber jabber, see what the question is asking, and get on to solving the problem.

The alternative is to specify the problem in purely dense mathematical terms. However, I think this way is much better because to understand what the question is really asking without getting into this "eggs break easily" stuff is actually common sense. If someone can't use common sense to figure out what the question is asking without coming up with second grade smart aleck reasons why the problem doesn't work then I think the interviewer would have the answer they would looking for out of the exercise anyway. :)

The author didn't create the problem, he just wrote about it :)

Suspension of disbelief: https://en.wikipedia.org/wiki/Suspension_of_disbelief

"This is a math puzzle plain and simple."

You're being asked to accept that it's possible for an egg, or some other fragile object like, say, a baby, to survive a drop from the first or any other floor, and proceed to solve the math problem.

I agree with both you and the parent post. The article definitely asks for the suspension of disbelief and to be treated like a math puzzle.

However, I think it would be a valuable exercise to try and make a more formal statement of the situation so that the parts of the problem that don't line up squarely with the premise (i.e. eggs often crack when dropped from ~4ft high) were more explicit.

That way, the problem could be introduced both ways at the outset, so that you have the motivating image along with the actual constraints of the problem.

I know that an unprotected egg will smash when dropped from one story, guaranteed.

I've heard this problem specified as involving fossilized dinosaur eggs in order to get around this problem.

I wonder if it would avoid this kind of objection (which always comes up in logic puzzles) if problems was first stated in mathematical terms, and then analogized to a real world scenario. Something like ...

Assume two sets of integers (1..n) and (n+1..100), where 1 <= n <= 100. Your goal is to discover the value of n by asking whether a given number falls within set 1 or set 2. If you propose more than one number that belongs to set 2, you can propose no further numbers. What is the maximum number of proposals necessary to determine n?

If it helps, you can analogize this problem to dropping two fragile objects out of a 100-story building or something. Just don't forget the failure mode of "clever".

I agree here. My first thought was that you optimize for the two floors and forget about most of them. One of the best skills you can have when solving real world problems is to recognize when they're specifically not general case math problems and take the appropriate short cuts. If it weren't an egg, it would be a different story. But the problem specifically says it's an egg. Not a bowling ball or a chair or any other semi-resilient object that could survive an arbitrary fall. Details like that matter.

Exactly my thought. This could have been a test of over analysis. Though he wrote it should be considered as a simple mah problem and nothing more,

That was my first thought as well. My answer would have been something along the lines of, "Given my domain knowledge of eggs and sidewalks, I can estimate that the egg will survive a fall of at most zero or one stories. Therefore the best algorithm is a linear search starting from the 0th floor."

another critical error is damage to the egg (or any object) from each 'successful' drop.

An object that survies from being dropped from height x may not survive being dropped a second time from height x.

As my physics prof used to say with a smirk to all such "clever" retorts to questions he posed: "assume a spherical chicken of uniform density".

The author states that the solution is: 14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99, 100, which takes at most 14 drops.

In fact, that is a solution, not the solution, for this also works, and takes at most 14 drops: 9, 22, 34, 45, 55, 64, 72, 79, 85, 90, 94, 97, 99, 100.

Darn...too late to edit.

Note that if the number of floors is 105 instead of 100, then you can still do it in 14 drops, and the solution is unique: 14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99, 102, 104, 105.

The two solutions given above for 100 floors can be derived from the 105 solution. To get the solution given in the article, use the 105 floor solution and if it calls for dropping from a floor above 100 pretend that you did that drop and the egg broke, and don't actually count that drop in your drop count since you didn't actually do the drop.

The get the solution I gave, take the 105 floor solution, and shift it down 4 floors, so it ends on 100 instead of 105.

Many more solutions are possible by mixing the ideas of pretending that floors about 100 break, and by shifting all or part of the 105 solution down.

From the text:

We now have all the information to compute the optimal two egg solution.

While I prefer to read about algorithms and strategies in the fashion the author writes, I'm a bit sad that there's is no proof (or informal reasoning) why this is the optimal solution. Does anyone have a paper or some reasoning which will make me believe that this is the optimal solution?

When you break the first egg, the worst case is the difference between the current floor (where the egg broke) and the previous floor (where the egg last survived). So, the worst total number of drops is the number of drops for the first egg (until it breaks), plus the above difference. If you try making the maximum difference less than 14, you run into problems with the first number...

The problems with optimizing worst case are much simpler than optimizing the average case (you don't have to deal with probabilities, and you don't need to know the distribution of egg hardness). So, the proof, and the complexity of the proof, depends on what "optimality" measure you choose.

I was asked this question in a google interview earlier this year. Neither I nor the interviewer got past the "every 10 floors" approach (though I did make it through that round of interviews!). Interesting to see there was more meat on that bone.

I think that "every 10 floors" approach is optimal for average case.

Basically, E(number of drops) = E(number of drops for 1st egg) + E(number of drops for 2nd egg). We know that E(number of drops for 2nd egg) = 1/2 the difference between two drops of the 1st egg, and E(number of drops of 1st egg) = 1/2 the number of intervals, and 100 = the number of intervals × the difference. So, we're minimizing x + y, knowing that x × y = 100. Since the problem is symmetric, x and y must be equal, namely 10, so "every 10 floors" is the correct answer.

Actually there's a slight optimization available. Why ten floors? Because basically what we are doing is establishing a most significant digit - the tens place, then the ones place. This works because 100 is a square number (10*10). But what if there were 64 floors? Then, to do the same thing (but in base 8), we'd drop every 8 floors. We can account for this as we drop by treating all floors above as a fresh tower and rounding to the nearest square number: Drop on floor 10 (90 floors remain - 81 is closest square, so now only go up 9 floors), drop on 19 (81 floors remain, go up 9 again), drop on 28 (72 floors remain, 64 is closest square, go up 8), etc, etc.

This seems to be false:

    eggs :: [Int] -> Int -> Int
    eggs drops floor =
        if floor >= last drops
        then (length drops) - 1
        else let numless = length $ filter (<= floor) drops
                 below = last $ filter (<= floor) drops
                 above = head $ filter (> floor) drops
              in numless + (floor - below) + (if floor + 1 == above then 0 else 1)

    sum $ map (eggs [0,10 .. 100]) [0..100] -- returns 1100
    sum $ map (eggs [0,14,27,39,50,60,69,77,84,90,95,99,100]) [0..100] -- returns 1047

(Not 100% confident that I haven't made a mistake. You pass "eggs" a list of floors to drop the first egg on, and the lowest floor that the egg will survive being dropped from. It returns the number of drops it takes to discover that value. The list needs to start with 0 because that requirement simplifies the function slightly.

But if I haven't made a mistake, "10, 20, 30..." takes an average of 10.9 drops and "14, 27, 39..." takes an average of 10.4. That's assuming the floor is uniformly distributed between 0 and 100 inclusive.)

> E(# of drops) = E(# of drops for 1st) + E(# of drops for 2nd)

In the general case, I don't think this is true. I think you're relying on the idea that all intervals are equally large. But I'm not definite here.

> E(# of drops for 2nd) = 1/2 the difference between two drops of the 1st egg

Sure, but this depends in a nasty way on your schedule for dropping the first egg.

> E(# of drops of 1st) = 1/2 the number of intervals

This is definitely wrong. Say my schedule for dropping the first egg is [1, 2, 3, 100]. On your analysis, the expected number of drops the first egg will take to break is 1.5. If we assume that the egg's breaking threshold is uniformly distributed over floors 1-100, the actual expectation for drops-to-break-the-egg is 3.94.

> 100 = the number of intervals × the difference

True for the average difference, but this is pretty explicit about assuming that the size of an interval is constant.

>> "E(# of drops) = E(# of drops for 1st) + E(# of drops for 2nd)"

> "In the general case, I don't think this is true. I think you're relying on the idea that all intervals are equally large."

Pretty much.

More explicitly, the grandparent is relying on the assumption that E(egg2) is independent of what happens to egg1, which is only true if the interval sizes are the same. In the article's solution, E(egg2) is dependent upon which interval egg2 is dropped in -- if egg1 breaks on the first drop, E(egg2)=7 (the center of the 1-13 interval) but if egg1 breaks on floor 100, E(egg2)=0 since we already know floor 99 is safe.

To calculate E(egg1 + egg2) we need to compute something resembling a weighted average. A quick-and-dirty excel chart gives me an expectation of 9.97, whereas intervals of size 10 give an expectation of 10.5 (first egg gets 1-10 drops for an expectation of 5.5; second gets 1-9 drops for an expectation of 5.0 as the tenth drop would be a repeat.)

I predict that the overwhelming majority of people who correctly solve this problem under interview conditions have seen it before.

I was asked that question, with glass bulbs instead of eggs, at an interview last year. I don't think I found the optimal solution of 14, IIRC I got to the point (just talking aloud to the interviewer, no paper) of saying something like "so if we started at, say, floor ten, we'd have nine floors below, and something close to that sets of floors above if we needed to move up..." and he said something like "ok, cool, that's good, let's move on."

I could've asked for paper, I suppose, but something about the word "puzzle" makes me want to puzzle it out in my head.

So my question for any interviewer types who ask puzzle questions is: do you prefer a candidate to go all the way to working out an optimal solution on paper, or is it really more about "the approach"?

In my experience it is more about "I heard you were supposed to ask questions like this on tech interviews, so I'll ask it even if I myself am shaky enough on the mathematics behind it that I simply know the One True Solution I read online".

What isn't explained, is why the solution that 'make(s) solutions to all possible answers the same depth' is also the solution that minimizes the average number of attempts needed for many (sets of) eggs. The motivation given is to reduce the worst case. That doesn't explain why there isn't perhaps a solution with a worse worst case, but a lower average number of drops.

Indeed it is not obvious. For example there are clearly cases where there are solutions with the same worst case and different worst cases. And in the slight variation where the cost of dropping an egg is the height at which you drop it, the solutions that reduce worst cost and average cost tend to be different.

And the next question:

What strategy should you adopt to minimize the number of steps it takes you up and down the stairs to find the solution?

That version seems too simple to be interesting. Let there be n floors. In the worst case you'll have to walk to the top floor from the ground floor in case the answer happens to be n-1. Therefore you can't do any better than n-1 steps in the worst case, so the obvious strategy of alternating dropping an egg and walking up one floor until you break the egg is optimal and takes n-1 steps and n-1 drops and only requires 1 egg.

You have to go down and pick up the unbroken egg.

Good point! That adds a lot of nuance. With several eggs, if you drop one egg and it doesn't break, you have the option of postponing the pick-up until later or leaving it on the ground altogether. Let me think about it.

I had a quick go at it using memoized minimax search. I assumed that picking up any dropped eggs is automatic when you're on the ground floor, but it would also be easy to model it as an action.

https://gist.github.com/3157191

Let me know if this is what you had in mind.

Can you see if the egg is broken without going down? I guess you're assuming so.

Take the elevator :)

I was asked this question once and I said "This is a common, widely discussed interview question on the internet. Are you trying to find out how smart I am thinking on my feet or whether I surf the web, because in practice, on the job, I'd be doing the latter to find out the answer. If you have genuinely unique problems here, you can do better than that."

And yeah, didn't get that one. Oh well. "Brain teasers" with thoroughly documented, widely-read solutions leave you with a Bayesian problem: You'll have the 0.5% geniuses that can come up with the answer in 2 minutes and 5% of people that have read the answer but will make you believe that they are geniuses by not disclosing they have read the solution.

In other words, you'd probably get 90% cheaters and 10% smarties.

Wouldn't the absolute best way (assuming you have never seen an egg before and do not know anything about eggs) would be to try and crush one egg in a vice grip to determine the strength of the outer structure and then infer a fuzzy-ish height/speed limit from that?

"There are no tricks, gotchas or other devious ruses. Don’t rat-hole with issues related to terminal velocity, potential energy or wind resistance. This is a math puzzle plain and simple."

Not within the rules!

"There are no tricks, gotchas or other devious ruses. Don’t rat-hole with issues related to terminal velocity, potential energy or wind resistance. This is a math puzzle plain and simple."

Not out of the rules either (according to what you just posted). At some point you need to crush an egg.

If the rules are implying that you can only do X and we are only looking for solution Y then why are we even talking about this? We may as well have a discussion about trains leaving from Chicago and New York and debate what city they will intersect from on a given day.

"This is a math puzzle, plain and simple" is the give away.

Well frankly, as a aero/mech engineer I'd definitely pull out the UTM and the aero chamber. Your vice grip isn't going to be enough. [For those wondering, first the aero chamber to determine Cd and terminal velocity. Then the UTM be used to determine the compressive strength.] After that I'd scan the other egg in a 3D scanner and generate a super accurately detailed model. Once the model is ready, it's just a matter of plugging these values into Ansys explicit dynamics or Comsol multiphysics and find out the exact height at which the egg will break. Granted, you might require a bunch of the world's fastest super computer clusters and a few days to solve this problem, but hey you have a very high accuracy and precision. [Probably +_ 1cm even].

But yeah, since the author has stated it's a math problem we've just left it as a thought experiment.

I blogged a solution in German in 2008: http://bjoernguenzel.de/2008/03/18/weiteres-matheratsel-die-...

If I was interviewing someone with this problem, I would want to hear what questions the interviewee asked, such as: "Do you want to optimize for best average or minimizing the worst case?"

He doesn't write down the math in the general case for the number of floors F(e,d) that you can check with e eggs and d drops:

F(1,d) = d

F(e,d) = sum k>0. F(e-1, d-k)

The sum can given a closed form solution for e > 2, just like for e=1 and e=2.

Another thing is that he directly solves the quadratic, but in fact n^2/2 < n(n+1)/2 < (n+1)^2/2. So taking the square root of twice the number of floors will get you either give you the number of drops you need with 2 eggs, or will under count by 1. It's easy to check which that is.

A more generalized version of the problem was posted as a practice question in Google's codejam contest:

http://code.google.com/codejam/contest/32003/dashboard#s=p2

I suggest solving this version of the problem, as it forces you to look at the problem from various perspectives. If you're stuck you can download solutions from the dashboard (link in top right corner).

Asymptotically, the question with more coconuts is more interesting. I haven't verified this for sure (there are some assumptions), but:

With the "naive" asymptotically correct solution (go up a constant number k of floors, then linearly search the remainder), two coconuts gives us a worst case cost of:

n/k + k

minimize for k, we get a cost of

2n^(1/2)

With 3 coconuts, we have

n/k + 2k^(1/2)

minimize for k, we get

3n^(1/3)

What happens when we get log(n) coconuts?

log(n)n^(1/log(n))

= O(log(n))

Sweet! So at least we can see that it converges to binary search as we add coconuts.

This problem has multiple solutions, as demonstrated by the HN comments. It's not asked to find a solution, instead to figure out your thought processes. You could come up with a comp sci solution (analogous to a data structure or algorithm), or a mathematical solution, or a physics solution or something different.

You'd have to shape your answer to the position you're applying for. The article would be perfect for a programming position, above and beyond what I could ever hope to achieve.

This isn't a critical thinking problem, it's a math problem. As a critical thinker, I would estimate what floor I think the egg would break at, then estimate a safe floor I feel the egg won't break at. The more eggs I have, the less safety margin needed. After finding the first "safe" floor I would go up floor by floor (or more than one floor at a time if I had spare eggs).

> then estimate a safe floor I feel the egg won't break at

This isn't a solution to the problem. Your approach carries the risk that you never find the answer (given the preconditions). I don't think this qualifies as "good" critical thinking, since you don't actually have a solution.

I would hate it to do it in an interview setting since the question didn't state the goal of finding the worst case scenario. It's like mind reading. I did solve it once during lunch with colleagues when we asked each other puzzles, which was fun.

Is people ok with posting the solution here? Or want to try out some more?

Hint: square root.

Part of an interview should test communication skills as well.

In the real job's performance you'll get ill-defined specs; it's sometimes more important to know to ask the right questions rather than solve perfectly the wrong problems.

Interviewers are humans, sometimes tired, and an ill-defined question is likely to appear sooner or later. Asking the interviewer if he meant worst-case has the potential to bring lots of bonus points for you; at least it would in my book.

Again you expect the interviewee to read your mind that he should ask a particular question. The puzzle is set up with certain conditions and boundary to see how the interviewee performs with those constraints. If one of the terms of the puzzle can be changed, then other terms can be changed, too. I would just replace the egg with a steel ball and be done with it, like just in real life you can just push the boundary and replace the meaning of the question completely.

Is binary search until the first egg breaks and then increment by 1 for the second egg the best approach?

No. If you first test is at floor N, the two possible consequences are:

- egg breaks: you know you the answer is in [1,N], and will have to start stepping by one floor until the second egg breaks

- egg does not break: you know the answer is in [N+1, max], and you still have an extra egg to play with.

There is an asymmetry here. Because of it, assuming that you can improve upon binary search, N should be less than at half the maximum height. That gives you less information, but decreases the chance that you get into the 'only one egg in hand' endgame.

Hmm I'm not following. What do you do with the first egg if it doesn't break?

You could continue the binary search but that's not relevant anymore - the problem is to minimize the worst case, and your worst case is 51 while there exists a solution whose worst case is 14.

You keep using it. Binary search is the right way of thinking about it, but in some sense you haven't really created an even split by dropping the egg from floor 50 - because you know that you can figure out the correct floor faster using two eggs than one, you could check floors 51-100 much faster than you could check floors 1-50 (Even if you just did the naive binary search approach you first applied - i.e. if the first egg didn't break on floor 50 then drop it from floor 75, and then after that use the second egg to check each floor, it would only take you <=25 goes to find the right floor in 51-100, wheras it would take you up to 50 goes to find the right floor in 1-50).

So the correct floor at which to make the first drop is clearly not floor 50. If you dropped the first egg from floor 40 you would do better - it'd take you up to 40 goes to find the right floor if it's below floor 40, and up to 31 or so goes to find the right floor if it's above (because you can reuse the first egg to check whether it's in 40-70 or 70-100). Floor 40 is in some sense a "more binary" place to drop the first egg from than floor 50.

If you keep following this line of thought, and remember that whenever you make your approach more efficient, you can recursively apply that more efficient approach to "what do I do if the first egg doesn't break", you'll arrive at the solution given in the article.

Lots of interesting stuff in that blog, be sure to check it.

How about this solution: It's an egg. It will break from the hight of even 5 feet. The answer is the first floor.

As solved mathematically here http://www.trungh.com/2010/12/light-bulbs/

Start dropping the first egg at floor 1, if it doesn't break, then drop it from floor 10, then 20, then 30, then 40, etc until it breaks. Say the egg breaks at floor 30, start dropping the other egg from floor 21, then 22, then 23, until it breaks. Very easy problem.

Reply on news.ycombinator.com