We are given $N$ coins which are identical to each other with the exception of only 1 fake coin which is slightly heavier. The problem is to find the heaviest coin. We also have a Balance Scale. One operation is to put a set of coins in the two sides of the scale and the answer of the operation is whether it balances to a certain side.
Find the lower and upper bound for the above problem so that the two bounds coincide.
The classic algorithm that solves the Balance puzzle problem gives the number of weighings in $\log_3(N)$ weighings for $N$ coins so I guess that's an upper bound. How can I find the lower bound for this problem?