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.
[Math] N marbles puzzle: find the heaviest among them.
algorithmsdiscrete mathematicspuzzle
Related Solutions
Your solution can work as well as many others, like e.g.
6v6/0 -> 2v2/2-> 1v1/0
where XvY/Z means weight X against Y, keep the heavier of them if any, Z otherwise.
Your solution has the merit to possibly require less weights in 2 cases out of 12, of course, although it can be improved a bit like this (I hope the notation for the arrow is self-explanatory):
3v3/6 -XY-> 1v1/1
-Z--> 2v2/2 -> 1v1/0
which requires only two weights in half of the cases.
Note that you can use up to 2 weights if you have no more than 9 marbles, because you can solve 9 marbles as follows:
3v3/3 -> 1v1/1
So, another perfectly valid solution to the 12 marbles puzzle might even be:
2v2/8 -XY-> 1v1/0
-Z--> 3v3/2 -XY-> 1v1/1
-Z--> 1v1/0
which requires only two weights in one third of the cases.
In general, if you have N weights at your disposal, you can solve the puzzle up to $3^N$ marbles included. With three weights, you can then have up to 27 marbles:
9v9/9 -> 3v3/3 -> 1v1/1
and it's basically the extension of a binary search with three alternatives instead: you can generally divide your lot into three partitions, and have a way forward by comparing only two of them.
Using only weighings with one coin on each side, one can prove that the ordering can be determined with seven weighings:
Weigh coins $A$ versus $B$, then $C$ versus $D$, and then the heavier in each pair against each other. We can re-label the heaviest found as $D$, its original partner as $C$, and the loser of the "weigh-off" as $B$. These three weighings have led knowledge that $D>B>A$ and $D>C$.
Next weigh the coin $E$ (which has thus far not been touched) against $B$, and then against $D$ if $E>B$, or against $A$ if $E<B$. These fourth and fifth weighings tell you the exact order of $D, E, B$ and $A$. For example, you might find that $D>B>A>E$. It does not matter which of the possibilities you find; the important facts are that you know the order and that the second lightest and the lightest are not $D$.
For the sixth weighing, weigh coin $C$ against the second lightest of the other coins. In our example, we would weigh $C$ versus $A$. Then the only doubt left is the relative weight of $C$ and just one other coin. In our example, if $C>A$ then we can complete the full ordering by weighing $C$ versus $B$ because we already know that $D>C$.
Thus the seventh weighing determines the complete order.
The way to figure this out was:
Without loss of generality, one can assume that the first weighing tells you that coin $B$ is heavier than coin $A$ (written as $B>A$). Then there are only two classes of choices of next weighings:
(1) Weigh coin $C$ against coin $A$ (or any equivalent weighing against an already-weighed coin): Here, a possible result is $C>A$ which leaves 40 allowed orders. Since each weighing provides only one bit of information, discerning among $40$ orders requires at least six weighings, for a total of eight.
(2) Weigh coin $C$ against coin $D$ (or any equivalent weighing of two not-yet-weighed coins): Then there are three classs of next weighing choices available.
(2a) If the third weighing is $E$ versus $D$ (or any of the already-weighed coins) then one possibility says that $E<D$, which leaves $20$ allowed orders, requiring at least $5$ further weighings, for a total of eight.
(2b) If the third weighing is $D$ versus $A$ (or equivalently $B$ versus $C$) then the answer $D>A$ leaves $25$ possible orderings (slotting $E$ into any of $5$ positions, with the first four ordered $DCBA, DBCA, DBAC, BDAC$ or $BDCA$) which again requires at least $5$ further weighings, for a total of at least eight.
(2c) If the third weighing is $D$ versus $B$ (or equivalently $A$ versus $C$) then the answer must be equivalent to $D>B$. So $D>B>A$ and you can slot $C$ into any of three positions (but not into $C>D$) and then $E$ into any of $5$ positions. With $15$ allowed possibilities, it might still be possible to discern the ordering in only four more weighings.
So assume we have (in three weighings) $D>B>A$ and $D>C$. The next weighing needs to involve coin $E$ because if we weigh $C$ against $B$ or $A$ there will be some chance of leaving two remaining positions possible for $C$, thus two times five remaining allowed orderings, which cannot be disambiguated in only three further weighings.
3a) Say the next choice (the 4th weighing) is to weigh $E$ versus $B$ (this is the obvious one to try because $D>B>A$). Then if we find $E<B$ we will end up knowing that $D>B>E>A$ or $D>B>A>E$. We spend our fifth weighing on $A$ versus $E$ to fully order those four. Since we know $D>C$ we can now find where $C$ belongs in only two more weighings (starting from weighing $C$ against the second lightest of the others), for a total of seven weighings.
Similarly, if we find $E>B$ we will end up knowing that $D>E>B>A$ or $E>D>B>A$. We spend our fifth weighing on $D$ versus $E$ to fully order those four. And again we can properly place $$ in two more wiehings, for a total of seven.
(3b) If the fourth weighing were to be $E$ versus $A$ or $E$ versus $D$, then we would require eight weighings in the end.
Best Answer
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 $$