Tuesday, November 21, 2006

Biding My Time - The Answer

If you haven't read the original post where I asked the question, you may want to before reading the answer below. This question was asked of me in a telephone interview, and I managed to work out the formula below on the phone in about five minutes. I didn't go the extra step of performing the derivative and setting to zero on the phone - the interviewer was happy enough with the formula.


If you only had one marble/ball/egg, whatever, you would be forced to go serially from floor n to floor n+1 until it breaks and then floor n would be the answer. Since you have two marbles/balls/eggs, whatevers, you can use the first one to narrow down the scope. The question is how to do that narrowing most efficiently.

Assume you are going to divide the 100 floors evenly into groups of n floors, then the first marble can be dropped on every nth floor and when it breaks, the final marble only has to check the n-1 floors between the last two floors checked.

Let d be the number of drops and n be the number of floors per section for the first marble. In the worst case for d (which is what we care about) then:


d = 100/n + (n-1)

So now to find the minimum d with respect to n, we need to use some high school calculus to take the derivative and set to zero. This yields:

dd -100
-- = ---- + 1
dn n^2

-n^2 = -100

n = +/- 10

Since only positive numbers make sense in the scenario, we can see that we should drop the first marble from every tenth floor and then the worst case for the number of drops to find the floor in question is 19.

4 comments:

Eric said...

Your solution is not optimal; you made an unwarranted assumption. With two marbles and a 100 story building, it is possible to find the maximum height from which a marble can be dropped without shattering in a maximum of 14 drops.

I was also asked this question in an interview, and the interviewer told me that I should be able to derive the mathematical formula for the optimal solution. I came up with your solution, but recognized it as non-optimal. It took me about two hours this evening to find the optimal solution, and another hour to prove to my own satisfaction that is is optimal.

Hint: 14 drops are sufficient for buildings of 92 to 105 floors.

Eric said...

By the way, I don't think calculus will help with finding the optimal answer (though I could be mistaken). My solution was derived using only integers.

Anonymous said...

http://markonzo.edu can you do thi for me, ashley furniture [url=http://jguru.com/guru/viewbio.jsp?EID=1536072]ashley furniture[/url], cpaqlt, allegiant air [url=http://jguru.com/guru/viewbio.jsp?EID=1536075]allegiant air[/url], adhyvo, pressure washers [url=http://jguru.com/guru/viewbio.jsp?EID=1536078]pressure washers[/url], acxhh, dishnetwork [url=http://jguru.com/guru/viewbio.jsp?EID=1536080]dishnetwork[/url], jvjps, adt security [url=http://jguru.com/guru/viewbio.jsp?EID=1536076]adt security[/url], nniad,

Anonymous said...

http://lumerkoz.edu Gloomy tales http://www.ecometro.com/Community/members/Buy-Tamoxifen.aspx rosmini http://www.comicspace.com/maxalt_buy/ falsifying booklets http://malgorz.com/members/Buy-Isotretinoin.aspx dowd bawden http://www.lovespeaks.org/profiles/blogs/buy-enalapril theyve http://barborazychova.com/members/Buy-Cleocin.aspx fullerton