Sunday, April 12, 2009

A further remark on the orb puzzle

Here is a further remark on the orb puzzle also called the egg puzzle and (in)famously also called, because of interview forums, the 2 orb puzzle or the 2 egg puzzle.

Back here, in India, the object that guys have been using, since time immemorial, is an egg.

NOTE: In what follows, I would be using egg (and not orb) as the object of experiment. The title was chosen as "A further remark on the orb puzzle" as a homage to the mind of whoever first came up with this remarkable puzzle. Now you can gear yourself up for the further remarks, which to my best knowledge have not been accumulated elsewhere.

If you want to know what the puzzle and how to solve it, you can read my previous post.

Now that you have settled (assumption being you are aware of the puzzle and its solution) you can start reading what follows.

Somewhere, while doing the above question, my thoughts turned to a strange corner. I had solved the problem in its full generality and had also tried cases with different number of eggs and floors.

With 3 eggs, it took you 9 turns to cross 100 for the first time. With 4 eggs, this number was 8.

With 5 eggs, the number came out to be 7.

I started wondering, could I beat binary search with this method?

I just wanted to see the number of floors you scale when you were allowed 7 drops. Could it exceed 128?

I tried with 6 eggs. Answer? 126.

7 eggs. 127.

Using more than 7 eggs, as expected, gives 127 because max drops is 7. And thus, for the following number of eggs, I had

8? Again 127
20? Again 127.

I then had a look at floors scaled with 6 drops. The answer was 63. 63 appeared the first time (with 6 being the fixed number of drops) when I used 6 eggs.

127 appeared (with 7 being the fixed number of drops) the first time when I allowed myself at least 7 eggs. Wherefrom, it remained 7 regardless of the number of eggs.

Hmmm..Something was brewing in the mathematical universe. The number of floors scaled with a certain number of drops had an upper bound which could not be pushed by upping the number of eggs.

What was going on?

I found the answer in a pdf by Umesh Nair. Though he does not address this issue directly, the treatment he invoked for solving this question could be readily extended to solve my problem.

In particular, he made the interesting observation that if you are allowed a total of 'd drops' then you could not scale more than 2^d floors.

Once I read this statement, it was pretty obvious!

Can you see why?

The answer lies, as Mr. Nair points out, in the innocous fact that for a 'particular setting' ('e eggs', 'n floors', the 'break floor' being the b-th floor) there exists a unique sequence of drops which locates the 'break floor'.

You change the number of 'break floor', you see a different drop sequence emerge. There is, thus, a one-to-one mapping between drop-sequence and a 'particular setting'.

And therefore, the number of drop sequences equals the number of floors you scale for a particular setting.

And obviously, you have scenarios where you do not end up using all of your 'd drops' for a particular setting.

For example, even though in case of 2 eggs and 100 floors, you are allowed a total of 14 drops, if the 'break floor is 1' you can locate it in 2 drops! (not all 14 drops are needed).

Therefore, some drop-sequences are smaller in size. Which means that with maxmium 'd drops' you can really not scale unbounded heights as you increase the number of eggs. Further that bound is 2^d (as remarked above) because some drop sequences being smaller, terminate the entire sub-drop tree that could have been rooted at that position.

Because for the 2 egg, 100 floor, 1st floor-break-floor setting, drop sequence 1st-at-14 and 2nd-at-1 terminates; you cant have, in this particular case (where 1is the break-floor) any other trials after completing your 2nd drop.

This is pretty interesting analysis!

Hats off to Mr. Nair for his work on this problem!

He has made a few other remarks as well. For example, he has converted the original recurrence (which you can also find in my previous post) to a combinatorial summnation.

I will write about that later.

So far, so good.

But that still does not answer why this egg method converges with binary search when number of floors and number of eggs are in binary-search-tandem.

(That is floors are 2^e - 1 when number of eggs is e). In case, you are not sure it does, think a little bit about it; i will not answer it here apart from mentioning that you should be able to make it out from what has been said above.

Call it the tandem-issue.

Intuitively, we would expect someone not familiar with the recursive solution this puzzle boasts of, to come up with the binary search strategy only, given number of eggs and floors are in binary-search-tandem. (In fact, guys usually come up with binary search even when the values are not in that tandem - but that is not what I intend to discuss).

The fact that one comes up, on an intuitive level, with binary search given the tandem complimented with binary search information-theoretic content, maybe reason enough for someone to point out that this solves the tandem-issue.

But such a reasoning is not complete. We need to answer why in binary-search-tandem settings, does the recurrence become as good as binary-search itself. We should not invoke reverse reasoning. That is, we should not say that binary search is what we can use in tandem-issues and since it is known to be best, thats what we do.

We have also got the responsibility to answer why our-recursive-way will also proceed the binary-search way. Sure, it could have figured out a different way requiring the same number of drops differently.

Then why did not it do so? Why another mathematical cataclysm?

Now that we are clear on the problem, we solve it.

We just need to show that T(d, d) = 2^d - 1.

Try it on your own. I will answer it soon in this space only.

For now, its goodbye

No comments: