Fog Creek Software
Discussion Board

Orb solution, correction

The answer is not 14, but 12 since you can break both orbs
Pick a worst case scenario : correct floor is 13

drop the first orb at 14, it breaks
drop the second orb at 2, if it breaks, the answer is 1
drop at 3,4,5,6,7,8,9,10,11,12

If the orb hasn't broken, the answer is thirteen
and you have dropped at floors

2,3,4,8,9,5,11,12,16,7,10,4 == twelve tries

similarly the solution for 98 is
14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99, 97

Wednesday, July 24, 2002

nuts, posted too quickly

you would have to drop a at 13 in the first example
to make sure the correct answer wasn't twelve

assuming that the answer can't be zero, only the
floor == 1 would be doable in thirteen drops
so the correct answer is indeed fourteen, with
the possibility of thirteen if the correct floor is one

Wednesday, July 24, 2002

"drop the second orb at 2, if it breaks, the answer is 1"

Er... no... since you haven't dropped it at the 1st floor, you can't be sure it would break there.  It may be that the orb only breaks on the 2nd floor.

Of course, the amusing part of this is that you ARE correct, it is somewhat 13 drops in that particular scenario, because most buildings, by custom, are built without a 13th floor!  (or is it that the scenario doesn't exist because there is no 13th floor?)

You'd end up testing (breaks on 14) :
Drop 2nd orb on : 1,2,3,4,5,6,7,8,9,10,11,12 (13 drops).

However, I believe that is may be that because it is in fact a 100 story building, the top floor would be numbered 101, leading us to believe that the actual drop numbers would be :  15,28,40,51,61,70,78,85,91,96,100, 101

Of course, we're once again back to a maximum of 14 drops.

The question becomes interesting again if you examine it in the possiblity that you have 3 or more orbs to sacrifice in the scenario.

In the case of 3 orbs, I can see where you reduce your legwork in the same building to a maximum 9 drops.

Orb 1 / Orb 1 breaks, drop Orb 2

38 /  8, 16(no 13th floor), 22, 27, 31, 34, 36, 37
67 / 45, 51, 56, 60, 63, 65, 66
89 / 73, 78, 82, 85, 87, 88
101 / 94, 98, 100

Three questions I'll leave, just for fun :

1) For three orbs, how many floors (or what is the top floor number) that you can test the orbs to a maximum of 9 drops?

2) Can you define mathematically the solution illustrated here?

3) I haven't worked my way through it yet, but I believe given N orbs, and Z floors, there should be an algorithm to determine the maximum number of drops necessary.  I may play with this later.  I find this disturbingly familiar, like the a name on the tip of my tongue that you just can't remember.

Stephen Hoffman
Wednesday, July 24, 2002

*  Recent Topics

*  Fog Creek Home