Finding upper and lower bounds of a problem

Question

We have n balls where 1 is a little heavier than the others and we want to find that heavier ball. We can only put some balls on one side of the scale and some on the other side and see if it leans and to which side. How can we find lower and upper bounds for this problem? We want upper and lower bounds to be equal.

Answer 1

An upper bound is $m$, where $m$ is defined to be the value s.t.

$$2^m\leq n< 2^{m+1}$$

and this can be proven by induction:

Take any $2^m$ balls and note that there are $n-2^m<2^m$ left

Split those $2^m$ balls in $2$ groups of $2^{m-1}$ and weigh them.

If thery have equal weight, then the heavier ball is in the $n-2^m<2^m$ others and by the indiction hypothesis we can find the heavier one with at most $(m-1)$ weighs. Thus at most $m$ weighs

If they have different weights, then the heavier ball is in the heavier pile.

Hence, $[\log_2(n)]$ will suffice.