3

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!

blues5938
  • 73
  • Compare $a_1a_2$ vs $a_3a_4$. Suppose they are equal. then compare $a_1a_2$ to $a_5a_6$. Suppose they are equal. Compare $a_1$ and $a_7$. Done. – A.S. Nov 16 '15 at 00:18

2 Answers2

5

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$.)

Arthur
  • 199,419
  • Clear and concise, thanks. Does it matter which four coins you choose if the weighing was originally unbalanced for $ABC$ vs $DEF$? – blues5938 Nov 16 '15 at 00:33
  • @J.Andrews Yes and no. It is somewhat important that in each dish there is one coin that was already there from the last weighing, and one coin from the other dish. So it could've been AE vs BF or CF vs AD, but not AC vs BD (although, as I've pointed out in my answer, we're so far from the real potential of the procedure that you would still be able to wring out an answer form only one more weighing in that case). – Arthur Nov 16 '15 at 00:35
0

Basically your first weighing has to be ABC vs DEF or AB vs DE. You have shown that ABC vs DEF works in two weighings if the first one balances. Next show that you can get there in three if the first one does not. Now you have shown that three are sufficient. To show that it cannot be done in two, consider AB vs DE. In this case you fail if it balances. You have four coins and can't find the odd one in one weighing, because there are three places for coins (two pans and off the balance), so there will be two unknown coins in the same place. This shows three are required.

Ross Millikan
  • 374,822