Let your first weighing be ABC vs DEF. If it's balanced, then you know that the fake is either G or H, and that can be checked with a single weighing, for instance G vs A.
If the first weighing was unbalanced, next weigh AD vs BE. This can go one of three ways:
- It's balanced. That means that either C or F is counterfeit, which can be checked with a single weighing.
- It goes the same way as before (i.e. ABC and AD were both the heaviest, or they were both the lightest). In that case, the counterfeit coin stayed in its dish, which means it's either A or E. Do a single weighing to decide which one of them is counterfeit.
- If it went the opposite way of the first weighing (i.e. ABC was heaviest and AD was lightest or the other way around), that means that the counterfeit coin changed sides, which means it's either B or D. Either way, you only need one more weighing to figure out which one it is.
This method can actually be expanded all the way up to $12$ coins, following roughly the same procedure, and still managing in only $3$ weighings. (Note that none of the final weighings are with only two candidate counterfeits, when you can easily handle $3$, and in the case where the first weighing is balanced, you only need two total weighings. That leaves a lot of room for a bigger pool of coins, and that limit happens to be at $12$.)
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
For a, let there be $m=5$ coins. We can call them $A,B,C,D,E$. It is asserted that there are $2 \cdot 5+1=11$ possibilities. Either one of the coins is heavy ($5$ possibilities because it can be any coin), all the coins are correct, or one of the coins is light (again $5$ possibilities.)
For b, let us continue with $m=5$. Each weighing has $3$ possible results. If we weigh twice, there are $3 \cdot 3=9$ possible results. As we can only distinguish $9$ possibilities with two weighings, it must take at least $3$ weighings to find a possible fake coin among $5$. You determine $n$ by finding the smallest $n$ so that $3^n \ge 2m+1$ so you can distinguish enough possibilities. This does not prove that the coin can be found in $n$ tries, it only proves that it cannot be found with certainty in $n-1$. To prove that $n$ will work, one needs to lay out a strategy of weighings.
$m=5, n=3$ should be easy because $3^3=27$ is so much more than $11$. We first weigh $AB$ vs $CD$. If they balance $ABCD$ are all good and we weigh $E$ against any other coin and have the result. If $AB$ are heavier than $CD$ we can have either of $AB$ heavy or $CD$ light. We can then weigh $AC$ against $BD$. If $AC$ is heavy either $A$ is heavy or $D$ is light. We weigh $A$ against $B$ and have the answer. The other results are similar. We have shown that $3$ weighings suffice for $m=5$ coins.