Fog Creek Software
Discussion Board

orbs solution

Yes, I saw the (correct) provided solution.  The one below is meant to show how you can get to it (which you can also reuse if the problem parameters are changed)


Denote the floor from which we drop the first orb with k.  For any k, let's call n(k) the height of the tallest building for which the correct floor can be identified from k drops.

If the first orb breaks, we need k overall drops to determine the correct floor (which is then below k).  If the orb did not break, we are left with h = n(k) - k stories.  Now if h was greater than n(k-1) then the task could not be completed for the upper part because n(k-1) is the most floors for which k-1 drops are enough; if however h was smaller than n(k-1) then the building could be increased and the task still be completed with k overall drops which contradicts with our presciption that n(k) is the tallest such building.  Thus h = n(k-1), i.e. n(k) = k + n(k-1), a recursion which is solved together with n(0)=0.  The tallest building for which the correct floor can be determined by k drops is of height n(k) = k*(k+1)/2.

Now, 100 falls between n(13)=91 and n(14)=105, (the size of the tallest buildings for which 13 and 14 drops are enough, respectively) thus you should need at most 14 drops.  You can start from floor 14, but starting from 13,12,11,10 or 9 are also good enough because the remaining upper section will still not be larger than n(13).

Tamas Hauer
Tuesday, January 4, 2005

That's brilliant, I like the reasoning so much. How did you arrive at that? :)

Christian Kamel
Monday, January 10, 2005

You know, a good SQA person will tell you that the answer cannot be determined for certain. Here are some of the many reasons an answer cannot be certain:

1) Your height granularity is a single floor. What about partial floors.
2)  You make the assumption the floors are equally spaced. They may not be.
3)  Are the floors logical or physical. Some buildings don't show a 13th floor in their elevator.
4) An orb failure at the third floor does not mean it will fail when dropped from all higher floors.
5) What constitutes an orb breaking? How big a chip is required to denote a break.
6) Then there are a zillion physical problems such as what is the force of gravity at the test site. Orbs have a rating of 10 floors but on what planet?

And it can get even more absurd. Smoking a joint will tell you that dropping both orbs from the same height can give you different results. Puzzle and programmers like to look at a solutions domain. SQA people look at the infinite failure domain.

Brian Parry
Tuesday, January 11, 2005

Hi Brian

Its good that U consider so many aspects before going for the solutions. I also luckily got the same solution as is given 14. But its will good if before putting so many questions over the puzzle U give it a try assuming all of it already satisfies or meets the condition... for getting the answers

Vivek Gupta
Tuesday, February 8, 2005

Brian, are you preparing for an interview at a management consultancy? If yes, I sympathize and shall not call you an ass.

Bombay Tapori
Friday, March 11, 2005

*  Recent Topics

*  Fog Creek Home