[Math] Counterfeit Coin Problem – 8 Coins

Question

How many weighings of a balance are necessary to determine if a coin is counterfeit among eight coins. The counterfeit coin is either heavier or lighter than the other coins.

I understand the reasoning behind this problem when you know how the weight of the counterfeit coin compares to the rest of the pile, but I can not think of how to show that this problem takes 3 weighings.

What I have so far is that say you have the coins $A B C D E F G H$, weigh $ABC$ against $DEF$ if they are equal then weigh $A$ against $G$ if these are equal then the counterfeit coin is coin $H$ if these two are unbalanced then $G$ is the counterfeit coin.

Now this is where I hit the wall. When the piles of $ABC$ and $DEF$ are unbalanced you know that $G$ and $H$ are not counterfeit. I think you can now weigh $DA$ vs $BC$ and in the case where $DA$ and $BC$ equal you know that $E$ or $F$ is the counterfeit coin, which can be determined with one more weighing.

I am unsure of where to go from here, any ideas?

Thanks!

Answer 1

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:

1. It's balanced. That means that either C or F is counterfeit, which can be checked with a single weighing.
2. 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.
3. 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$.)