wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> Glass Balls
        
(Message started by: Garzahd on Oct 11^th, 2002, 1:02pm)

Title: Glass Balls
Post by Garzahd on Oct 11^th, 2002, 1:02pm

The other puzzle went over well, so I'll try another one that I like. (Forgive me if I've got the wrong forum; this could also be classified in CS, since it's originally from topcoder.com's programming contest. But I think it's more a problem-solving/math problem than a programming one.)

You have B identical glass balls, and an F story building. You want to find out how resilient the balls are. You know there exists some floor N<=F, such that a ball dropped out a window of floor N will not break, but a ball dropped from floor N+1 will break. (N may be 0, in which case all dropped balls will break.)

You want to find N in as few drops as possible. What's the worst-case number of drops you must use to find N, given B and F?

Clarifications: Dropped unbroken balls may be recovered and dropped again. Once N is found, it doesn't matter how many unbroken balls you have remaining, only the number of drops it took you to get there.

A couple hidden sample cases (depending on how much of a challenge you want):

With 1 ball and 42 floors, 42 drops are required.

With 2 balls and 100 floors, 14 drops are required.

With 3 balls and 92 floors, 8 drops are required.

Title: Re: New Puzzle: Glass Balls
Post by James Fingas on Oct 11^th, 2002, 1:12pm

Are the glass balls anything like eggs?

http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_hard;action=display;num=1027808394

Title: Re: New Puzzle: Glass Balls
Post by Garzahd on Oct 11^th, 2002, 2:47pm

Man, I suck. I would have sworn I had read all those. Sorry about that.

Title: Re: New Puzzle: Glass Balls
Post by william wu on Oct 12^th, 2002, 11:17pm

Not a problem Garzahd -- there's a lot to read on this forum! :)