Fog Creek Software
Discussion Board




orb

Here is a slightly more general solution to the orb problem:

Let n be the number of orb-drops required
and N be the number of floors.

So, one of the orbs will be dropped from:
n, n + (n - 1), n + (n - 1) + (n - 2), ...
till it breaks, at which time the other orb
will be tried on every floor from one floor
above the previously tried floor.

The problem can be formulated as:

Minimize n
subject to:  n(n + 1)/2 >= N
        n is an integer

Solving the quadratic equation:
n* = ceiling( sqrt(2N + 0.25) - 0.5 )

When N = 100, n* = 14.

Velant Guy
Friday, July 18, 2003

I was sucked back into this problem/scenario very recently due to an email on the topic questioning one of my earlier responses.

The approach you use is interesting, but your formula is incorrect.

Example (3 floor building)

According to your supplied formula :

n* = ceiling( sqrt(2N + 0.25) - 0.5 )

For N = 3, n* = 2

However, if the orb breaks from floor 2 or floor 3, it requires THREE drops to ascertain this.  Drop from 3 (breaks), Drop from 1 (intact), Drop from 2 (breaks/intact indicating floor 2/3 respectively)

Similarly, this formula fails for buildings of 6, 10, 15 floors, etc...

I think the correct formula for a 2-orb system to determine the maximum number of drops to correctly ascertain the exact floor where the orb ceases to survive is :

minimize n, subject to : n(n+1)/2 >= N + 1, where n is an integer and N > 1

and then to : n* = ceiling( sqrt(2(N + 1) + 0.25) - 0.5 )
or n* = ceiling(sqrt(2N + 2.25) - 0.5 )

Stephen Hoffman
Tuesday, July 06, 2004

*  Recent Topics

*  Fog Creek Home