Ball drop: Difference between revisions
Oscarlevin (talk | contribs) Created page with 'Here is a nice optimization puzzle from the [http://www.mathsisfun.com: Maths is Fun] website. ==Puzzle== Pool and Billiard mega store Balls-R-Us wants to shoot a commercial fo…' |
m Spelling and grammar fixes. Also fix link. |
||
| Line 3: | Line 3: | ||
==Puzzle== | ==Puzzle== | ||
Pool and Billiard mega store Balls-R-Us wants to shoot a commercial for their new Nearly-Indestructible-Billiard-Balls-Are-Amazing brand billiard balls. The commercial will feature a crazed pool shark smashing | Pool and Billiard mega store Balls-R-Us wants to shoot a commercial for their new Nearly-Indestructible-Billiard-Balls-Are-Amazing brand billiard balls. The commercial will feature a crazed pool shark smashing billiard balls by dropping them from the top of a tall building, only to find that when he drops the NIBBAA balls, they don't break! To make the commercial as convincing as possible, the company wants to use as tall a building as possible, so they need to know the highest floor their billiard balls can be dropped from without breaking. | ||
While you have a perfectly good 100 | While you have a perfectly good 100 storey building to test out the procedure, the producers of the commercial have only given you two billiard balls and want an answer as soon as possible. You realize you could test out each floor in order (first floor, then second floor, and so on), since you can reuse a ball that does not break. But that might take FOREVER! Is there a faster way? What is the least number of times you would have to drop the billiard balls to guarantee finding the highest safe floor? | ||
==Variations== | ==Variations== | ||
| Line 13: | Line 13: | ||
==Links== | ==Links== | ||
[http://www.mathsisfun.com/puzzles/dropping-balls.html | [http://www.mathsisfun.com/puzzles/dropping-balls.html Dropping Balls] As described on Maths is Fun. | ||
[[Category: Optimization puzzles]] | [[Category: Optimization puzzles]] | ||
[[Category: Algorithms]] | [[Category: Algorithms]] | ||
Revision as of 04:59, 13 October 2010
Here is a nice optimization puzzle from the Maths is Fun website.
Puzzle
Pool and Billiard mega store Balls-R-Us wants to shoot a commercial for their new Nearly-Indestructible-Billiard-Balls-Are-Amazing brand billiard balls. The commercial will feature a crazed pool shark smashing billiard balls by dropping them from the top of a tall building, only to find that when he drops the NIBBAA balls, they don't break! To make the commercial as convincing as possible, the company wants to use as tall a building as possible, so they need to know the highest floor their billiard balls can be dropped from without breaking.
While you have a perfectly good 100 storey building to test out the procedure, the producers of the commercial have only given you two billiard balls and want an answer as soon as possible. You realize you could test out each floor in order (first floor, then second floor, and so on), since you can reuse a ball that does not break. But that might take FOREVER! Is there a faster way? What is the least number of times you would have to drop the billiard balls to guarantee finding the highest safe floor?
Variations
Of course we could ask the same question using a different number of floors, or a different number of balls. In general, what is the least number of test drops needed to guarantee finding the highest safe floor when you have <math>n</math> balls and <math>m</math> total floors.
Links
Dropping Balls As described on Maths is Fun.