OpenEuphoria

re: Puzzle

• Posted by Jesse Duke <dark at cyax.com> Aug 10, 2004
• 371 views

) No more loopholes. The balls are resilient, and
) aren't weakened byeach drop. Either they break, or
) they are fine. Um, any otherloopholes I'll close too.
) So no thinking outside the box!
)
) Unfortunately the pure binary search won't work,
) because if you guess50 first, and it's under, you
) lose your first ball (it breaks), and ifyou guess 25
) second, and it's under, you lose your second ball...
) andyou have no more to test with...
)
) It can be done in 19 tries like this (worst
) case):With first ball: 10 20 30 40 50 60 70 80 90 100
) *break first ball*With second ball: 91 92 93 94 95 96
) 97 98 99
)
) The second ball will break somewhere between 91 and
) 99, and you'llknow the top floor. If the ball breaks
) at 18, then it's: 1st: 10 202nd:11 12 13 14 15 16 17
) 18 , the above is the worst case.
)
) So, 19 tries. I can do it in 14 though....14 or less
) tries, no matterwhat floor it breaks on... (Guess
) how)Haven't figured out a general case algorithm yet
) though....

Interesting.  I was thinking of a binary + linear search at first.  Ie:

First ball: 1, 2, 4, 8, 16, 32, 64, 128.
Second ball: (point before breaking point)+1 to (point after breaking 
point)-1

Taking some real-world knowledge into account, we would assume that the 
balls would be more likely to break at a lower level than a higher one, 
so this type of test would automatically pander out to that.  ie: to 
determine that the ball breaks on the fifth floor, you would do: 1, 2, 
4, (breaks), 5 (found it).  Compared to 1, (breaks), 2, 3, 4, 5 (found 
it) for the 10x10 method.

However, 48 would be 1,2,4,8,16,32,(breaks), 33,34,35,36,37,38,39,40,...48.

(compared to 1,10,20,30,40,(breaks),41,42,43,44,45,46,47,48)

I'm not sure what method would yield 14 tries (worst case)... it seems 
that 10x10 would be the absolute best if the breaking floor were random...
(no hints... i'm trying to figure it out...)

) First drop is on 14: if it breaks,
) then dropping on 1-13 (at worst 13 drops)
) will find the right floor.
) If it doesn't break on 14, second drop
) is on 27: if it breaks, then dropping
) 15-26 (at worst 12 drops) will find the right floor.
) If it doesn't braek on 27, the third drop is on 39 . . .
)
) The sequence of drops until the first
) ball breaks is 14, 27, 39, 50, 60, 69,
) 77, 84, 90, 95, 99
)
) For b=2, the number of drops (d) for
) a given f  is the smallest d such that
) d*(d+1)/2 is greater than or equal to f.

Damn...