Wednesday, November 11, 2009

The 100 Floors Egg Dropping Puzzle

This one’s a classic. I don’t even know why I’m putting it here. But before we proceed, I’d like you to take a look at this awesome puzzle site. All puzzles on my blog are shamelessly lifted from there. :P

The Problem
So, the puzzle goes like this. You have two identical eggs. And you have a 100 storey building. The eggs could be very strong or they could be very weak. So, they could break when dropped from storey 1. Or they couldn’t break even when dropped from storey 100. You have to find out the lowest storey such that when an egg is dropped, it breaks. How can you do this in the minimum number of tries?

The Solution
The simplest solution to this problem is, well, simple. You drop an egg from storey 1. If it breaks, you know. If it doesn’t climb to storey 2 and repeat. Then to storey 3 and so on. This approach will take minimum 1 tries and maximum 100 tries. Not good enough.

But we have two eggs. Suppose we drop the egg from storey 50. If it breaks we know that the culprit storey is somewhere between 1 and 49. If it doesn’t we know it’s between 51 and 100. Then we can use the other egg to check which one. This way, we can get a minimum of 2 tries and a maximum of 51 tries. Slightly better, I guess.

Can we do even better?

7 comments:

  1. I don't think so. The fastest you can do is in [log(100)] = 7 moves, with 7 eggs. Given n < 7 eggs, the best you can do is I guess a binary search upto n-1 tries, and then use the last egg to linearly search the last interval. I'm fairly convinced, but too lazy to write a proof, so it would be great to see a surprise here ...

    ReplyDelete
  2. @Shanth - Follow the facebook discussion.

    As an aside, I hate having the same discussion at two places. I hope someone will integrate wave into facebook and blogger soon so we can have the same thing at both places.

    ReplyDelete
  3. Yeah, I saw the fb discussion, which is why I said my post was stupid. I just now, realised, that it wasn't clear from my second post. Yeah, I think I'll also go to the facebook discussion, the only thing is that, I usually see the blog on google reader before I log onto facebook.
    Yeah, a sort of meta aggregator would be nice.

    ReplyDelete
  4. where is the awesome puzzle site?

    ReplyDelete
  5. Thanks, someone recently asked me this question in an interview actually. There's also a nice explanation here:

    Egg Dropping Puzzle

    ReplyDelete