OpenEuphoria

Re: Puzzle challenge:

• Posted by Don <eunexus at yahoo.com> Aug 10, 2004
• 473 views

> > It's not original, but it's an interesting puzzle:
> > 
> > Part A:
> > You're doing tolerance testing on new high-strength crystal balls, and
> > want to find out how much height they can be dropped from. You've been
> > given two orbs to work with, and you intend to drop them from floors
> > of an office building with a hundred floors (starting at floor 1, just
> > above the ground).
> > 
> > Naturally, once one of your orbs breaks, you can't reuse it. Both of
> > the glass orbs are manufactured to the same grade, so they will both
> > break above a certain height, and both won't break below that.
> > 
> > What is the minimum number of 'drop tests' you have to perform to
> > identify the top floor from which the glass orbs will survive a drop?
> > (Worst case scenario)
> 
> One.
> Drop it from the ground floor and it breaks, that's the top floor from which
> the
> orbs will survive (worst case).
> 
> > Part B:
> > Can you generalise this to f floors and b balls? What if f = 1000000
> > and b = 500?
> 
> Worst case if b is given, is one: b.
> 
> Kat

If it breaks on floor 1 wouldnt that be the best case and not the worst?

At first I was thinking a binary search algo would work best, but its
possible with a low tolerance on both balls they will both break without
knowing the answer.

My personal guess (which is probably wrong heh) would be 51 drops for
worst case.  Start at floor 2 and move up in increments of 2.  When (if)
it breaks move down 1 floor to fill in the gap.  So (IMO) the worst case
would be having to move 50 times up to floor 100 and if it breaks so you
have to go down one floor and check 99 to see if it breaks there.

If this is the answer, the number of balls would make a difference as you
could try other schemes (like binary search) to figure it out faster.
If you only have two balls the algo (if I am right mind you) the worst case
would always be <number of floors>/2 + 1.

If (like your second example) you have enough balls the binary search algo
would work better.  For 1,000,000 floors you should only have to drop a ball
20 times or so to get your answer.


Don Phillips - aka Graebel
     National Instruments
     mailto: eunexus @ yahoo.com