N marbles puzzle: find the heaviest among them.

Question

Suppose there are $N$ marbles and a two-pan balance used to compare the weight of 2 things. All of the marbles weigh the same except for one, which is heavier than all of the others. How would you find the heaviest marble in minimum number of comparisons.This link explains for $N=12$ .I have tried solving for $N$ but haven't come up with any solution.How it be can generalised for $N$ marbles? Explain in detail.

Answer 1

Each weighing can reduce the number of possibilities to $1/3$ of that from before, using the same argument as in the example you linked. If you have $3^n$ marbles, then you need at least $n$ weighings to find the heavier marble. If you have $3^n < N \leq 3^{n+1}$ marbles you should need $n+1$ weighings--since $N$ is not a power of three, some weighings are not as 'efficient' as possible. (i.e. don't eliminate exactly $2/3$ of possibilities since possibilities are no longer divisible by 3. In the worst case scenario, $\lceil N/3 \rceil$ possibilities remain after an 'inefficient' weighing.) Thus the number of weighings needed is

$$\lceil \log_3(N) \rceil $$

Answer 2

Divide your marbles into three groups. Compare group 1 vs group 2. If they are the same then you know the heavier marble is in group 3. If group 1 is heavier then the heavier marble is in group 1. If group 2 is heavier then the heavier marble is in group 2. Repeat this process until you are comparing individual marbles. If you have a situation where you can not divide them evenly by three use marbles that have already been identified as normal to make up the difference. If the initial number of marbles doesn't evenly divide by 3 then make group 3 have one more or one less marble in it.

Each step will reduce the number of remaining (unidentified) marbles to a third (rounded up). So if there are N marbles after the $x^{th}$ weighing you will have only $\lceil\frac{N}{3^x}\rceil$ left. You want to continue until you get down to one. In the base case you'll have $N=3^x$. In the worst case $N=3^{x+1}-1$. So you will require $\lceil\log_3N\rceil$ weighs.