Lower-bounds of a given problem

Question

I have the following problem:

You have n objects that have identical weight except for one that is a bit heavier than the others. You have a balance scale. You can place objects on each side of the scale and see which collection is heavier.

Goal is to find the heavier object, with the minimum number of weigh.

I know the best algorithm that can solve this problem. Here is the pseudocode:

function findDiffWeight(L[1:n]){

   if(L.size == 1) return L[1]

   int x = sum(L[1 : n/2])
   int y = sum(L[n/2+1 : n])

   if(x>y)  call findDiffWeight(L[1 : n/2])
   if(y>x)  call findDiffWeight(L[n/2+1 : n])
}

But I am struggling with finding the lower bound for this problem. I don't think that there can be a better algorithm that can solve this in less than logn operations.

However how to prove it? Could you give me some idea about finding lower bound for this problem?

Answer 1

Your algorithm, which requires $\lceil \log_2 n \rceil$ weighings, is in fact not optimal. This paper proposes an algorithm which uses $\lceil \log_3 n \rceil$ weighings, which is optimal by the argument outlined by Tom van der Zanden. Let's assume for simplicity that $n$ is a power of 3, leaving the general case as an exercise. Suppose we are given $3^k$ objects, which we divide into three groups $X,Y,Z$ of size $3^{k-1}$. We weight $X$ against $Y$. If $X > Y$, we recurse with $X$; if $Y > X$, we recurse with $Y$; if $X = Y$, we recurse with $Z$. After $k$ such steps, we will have zeroed in on a single object.

For the lower bound, suppose that we only do $k$ weighings. There are $3^k$ possible outcomes of this weighings – each one can be either "left side heavier", "right side heavier", or "both have the same weight" – and each of them causes the algorithm to output a definite answer. Since any of the $n$ objects could be the heavier one, we must have $3^k \geq n$. This argument will make more sense after you review the $\Omega(n\log n)$ comparison lower bound for sorting.