There are n balls, among which m balls are lighter (and equally light with each other). We have a balance scale; how many times must we weigh at least, in order to find these m lighter balls? We obviously have a lower bound of $\log_3 \left( \frac{n}{m} \right)$ , but can this lower bound be achieved? What is the complete number of times needed? What is the strategy?
Add a comment
|