Undergraduate Problem Solving Competition
Problem 2 (10/21 - 11/4) - Glass orbs
a) You're doing tolerance testing on new high-strength crystal balls.
You want to find out how much height they can be safely dropped from.
You've been given two of these orbs, and you intend to drop them off
various floors of a 5-story office building. The floors are numbered
from 1 to 5, with floor 1 being ground level, and you may drop either
of the orbs from any floor you wish.
Once one of your orbs breaks, you can't reuse it.
You're guaranteed that both of the orbs will break at a certain floor
and both won't break below that floor. What is the minimum number of
drops you need to perform to find out what the most height the orbs
will survive is?
b) What about if you still have two orbs, but the company's offices have moved
into an n-story building?
c) How about n floors and k balls? What if you think about the problem in
reverse - that is, how many floors can you cover with k balls and
n drops? Any further generalizations are, as always, welcome.
current problem | rules | dates | old problems | results
155 South 1400 East, Room 233, Salt Lake City, UT 84112-0090, T:+1 801 581 6851, F:+1 801 581 4148