
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 .. n1)
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 M1 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 M2 times. Thus orb 1's second drop would be M1 floors above the first drop, or floor M + (M1).
In general, if orb 1 breaks on try n then orb 2 is allowed at most Mn drops, and the corresponding nth floor number is:
F(M, n) = M + (M1) + (M2) + ... + (Mn+1)
Note that n cannot exceed M, so the highest floor testable is :
F(M, M) = M + (M1) + (M2) + ... + (MM+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
