Fog Creek Software
Discussion Board




The Orbs solution is Incomplete

Well, it really inst' a sloution, if it doesn't describe how you get to find that sequence, the reasoning behind it.

Also where it states:
(n'+1 .. n'-1)
should be:
(n'+1 .. n-1)

Rui Martins
Wednesday, August 04, 2004

Here's the rationale:

Let M be the total maximum number of drops required for both orbs. 

If orb 1 breaks on try 1, orb 2 may be dropped at most M-1 times.  This requires that orb 1's first drop be from no higher than floor M.

If orb 1 breaks on try 2, we may drop orb 2 at most M-2 times.  Thus orb 1's second drop would be M-1 floors above the first drop, or floor M + (M-1).

In general, if orb 1 breaks on try n then orb 2 is allowed at most M-n drops, and the corresponding nth floor number is:

F(M, n) = M + (M-1) + (M-2) + ... + (M-n+1)

Note that n cannot exceed M, so the highest floor testable is :

F(M, M) = M + (M-1) + (M-2) + ... + (M-M+1)
= (1 + 2 + ... + M)
= M(M+1)/2

We need to test at least to floor 100, so we require

F(M, M) >= 100 :
or
M(M+1) >= 200

14 is the smallest positive integer satisfying this requirement.

The corresponding floor sequence would be:

14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99, 102, 104, 105

Since there are only 100 floors, the sequence ends: ..., 95, 99, 100.

Chuck Boyer
Thursday, August 05, 2004

There's a sense in which the given solution can be improved slightly.
The given solution was

14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99, 100

Now drop the first orb on the successive floors in this sequence and
suppose that we have just dropped the orb from floor 95 without
breaking.  Now if we continue with floor 99, we could take as many
as four more drops to find the desired floor -- drop 99 and breaks,
then 96, 97, and 98.  If we drop orb 1 from floor 98 instead, we
can reduce this to at most three drops. There are two possibilities.

Scenario 1: 98 breaks and then 96, 97.
Scenario 2: 98 doesn't break and then 99,100

Hence, the "best" solution should really be

14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 98, 99, 100

Glenn C. Rhoads
Friday, August 27, 2004

*  Recent Topics

*  Fog Creek Home