The Counterfeit Coin Problem
bobbejones
(2001-04-12)
You have 12 marbles, one of them is either heavier or lighter than the rest.
In three weighs on a balance scale, you must determine which is the odd marble.
How do you do this?
This one's a (great) classic. It has been presented in many different ways.
At one point, it was known as the Counterfeit Coin Problem:
Find a single counterfeit coin among 12 coins,
knowing only that the counterfeit coin has a weight
which differs from that of a good coin.
You are only allowed 3 weighings on a two-pan balance and must also determine
if the counterfeit coin is heavy or light.
Expanding on the question a little, we'll show that 3 weighings are enough to...
- Find an odd marble among 12 and tell if it's heavy or light.
- Find an odd marble among 13.
If you are given an extra regular marble, you may also...
- Find an odd marble among 13 and tell if it's heavy or light.
- Find an odd marble among 14.
(Please, understand that the extra "reference" marble is in addition
to the 13 or 14 "unknown" ones, but its presence makes the problem
simpler to solve.)
We'll also prove, in each case, that the above is the best that can be achieved.
First, let's deal with 12 marbles, call them ABCDEFGHIJKL:
First weighing: Compare ABCD and EFGH.
- If ABCD=EFGH, you know the special marble is among IJKL.
Use your 2nd weighing to compare AI and JK (you know A is ordinary):
- If AI=JK, you know L is the odd marble. You may compare L and A in the
3rd weighing to determine if L is heavy or light.
- If AI and JK are not equal, you know L is ordinary.
Use your 3rd weighing to compare J and K.
- If J=K, you know I is the special marble (the result of the second weighing
tells you if it's heavy or light).
- Otherwise, the special one is either J or K and you can tell which:
It's the heavier one if we had AI<JK on the second weighing,
it's the lighter one if we had AI>JK.
- If ABCD is not equal to EFGH, you know IJKL are ordinary
(we may use L as a known ordinary marble in the rest of the procedure).
Also, you will always know from this first weighing whether
the special marble is heavy or light, once you've determined which it is.
Use the 2nd weighing to compare ABE and CFL :
- If ABE=CFL, you know the special marble is among DGH.
You may use the 3rd weighing to compare G and H :
- If G=H, then D is the special marble.
- If G and H are not equal, the special marble
is the heavier one if we had ABCD<EFGH, and the lighter one otherwise.
- If ABE and CFL are not equal,
the special marble is among ABCEF and we may distinguish four cases :
- ABCD>EFGH and ABE>CFL :
Either F is light or one of AB is heavy.
Compare A and B in the 3rd weighing to find out.
- ABCD>EFGH and ABE<CFL :
Either E is light or C is heavy.
Compare C and L in the 3rd weighing to find out.
- ABCD<EFGH and ABE<CFL :
Either F is heavy or one of AB is light.
Compare A and B in the 3rd weighing to find out.
- ABCD<EFGH and ABE>CFL :
Either E is heavy or C is light.
Compare C and L in the 3rd weighing to find out.
The table below summarizes the entire procedure:
| First Weighing |
Second Weighing |
Third Weighing |
| ABCD = EFGH |
AI = JK |
A = L is not possible.
A < L Þ L is heavy.
A > L Þ L is light. |
| AI < JK |
J = K Þ I is light.
J < K Þ K is heavy.
J > K Þ J is heavy. |
| AI > JK |
J = K Þ I is heavy.
J < K Þ J is light.
J > K Þ K is light. |
 |
| ABCD > EFGH |
ABE = CFL |
G = H Þ D is heavy.
G < H Þ G is light.
G > H Þ H is light. |
| ABE < CFL |
C = L Þ E is light.
C < L is not possible.
C > L Þ C is heavy. |
| ABE > CFL |
A = B Þ F is light.
A < B Þ B is heavy.
A > B Þ A is heavy. |
|
| ABCD < EFGH |
ABE = CFL |
G = H Þ D is light.
G < H Þ H is heavy.
G > H Þ G is heavy. |
| ABE < CFL |
A = B Þ F is heavy.
A < B Þ A is light.
A > B Þ B is light. |
| ABE > CFL |
C = L Þ E is heavy.
C < L Þ C is light.
C > L is not possible.
|
With 13 marbles (ABCDEFGHIJKLM), you may follow exactly the same procedure,
ignoring the very existence of the extra marble M, except when the first two weighing
(ABCD vs. EFGH and AI vs. JK) come out even.
In this case, you have ruled out 11 marbles.
With 13 marbles, however, neither L nor M have been on the balance yet!
Comparing these two in the last weighing would thus not tell which one is special,
since it could be either the lighter or the heavier one.
Instead, you have to compare one of them (L, say) with an ordinary marble like A,
just as was done in the case of 12 marbles.
If L and A are not equal, you will know that L is odd and,
also, whether it's heavy or light.
Otherwise, you can tell that M is the special marble, but you
don't know whether it's heavy or light since M was never put on the balance at all.
In other words, the above table is still valid if you just edit the very first line
(which reads "A = L is not possible"
in the case of 12 marbles) so that it reads, in the case of 13 marbles:
"A = L Þ M is odd."
It's natural to wonder whether the above is the best we can do:
Is there a totally different approach that would allow us to determine whether
the odd marble is heavy or light with 13 marbles and/or to
detect an odd marble among 14?
The answer to both questions is no; the above is indeed the best we can do.
Let's deal first with the case of 13 marbles and show that you cannot possibly
know if the odd one is heavy or light in all cases.
Remark first that if n marbles are left out of the first weighing,
we will have to distinguish among 2n possibilities from scratch with just
2 weighings, in case the first one comes out even. As each weighing has 3 possible
outcomes, two of them lead to only 32=9 possible outcomes.
Therefore 2n must be less than 9, which means than n must be 4 or less.
With 13 marbles, this would imply that 9 marbles or more are involved in the
first weighing.
Since an even number of marbles are clearly involved in any weighing,
we would therefore have to compare two groups of 5 in the first weighing.
When this weighing does not come out even, we are left with exactly 10
possibilities: The odd marble could be any of the 10 that were put on
the balance (this first weighing does tell us, in each possible case, whether
the odd one is heavy or light depending on which side of the balance it was).
This would imply that the two remaining weighings could split 10 cases.
The absolute maximum being 9, this can't be done. (Same reasoning, of course,
if you involve 12 marbles instead of 10 in the first weighing, only much worse.)
Now, consider the case of 14 marbles.
Obviously, we can't find whether the odd marble
is heavy or light, but can we even detect it in all cases?
Answer is no:
The key observation is that, even if we do not care whether the odd object is heavy or
light, the weighing procedure will tell us in most cases: If the marble that's
eventually found to be odd was involved in any weighing at all, we will know
if it's heavy of light.
Now, remark that at each fork (or node)
of our decision tree there's at most one branch in
which the odd marble could be among the marbles that have not yet been weighed.
At the end, the only way the odd marble could be among the unweighed ones is if
all the weighings came out even.
This corresponds to just one leaf of the decision tree!
Therefore, any complete decision tree for n marbles would have at most
one marble appearing as the answer only once in a leaf, whereas the (n-1) others
must appear at least twice.
In other words, any weighing procedure that can detect an odd object among n
must have at least (2n-1) leaves.
If n is 14, this means 27 leaves, which is exactly what 3 weighing
would produce (27=33 ), if there's absolutely no "waste"
in the procedure. But we can prove that there must be waste in the "original" problem
(whereas the process can be made 100% efficient if we are given one extra
"reference" coin; read on). Indeed, the first weighing can involve only
2, 4, 6, 8, 10, 12, or 14 marbles and each of these introduce some inefficiency.
Let's consider only 8 and 10 (the other cases are even more wasteful):
If we put 4 marbles (or less) in each pan, everything is fine if the weighing comes out
uneven (we finish the deal exactly as with 12 marbles, or even easier if we had less than
4 marbles in each pan). However, we are in trouble if it comes out even, since
we have 6 unweighed marbles (or even more if we had less than 4 marbles per pan)
and the odd one is among these. We would therefore
have to build a decision tree with 2n-1 = 11 different leaves,
whereas the total number of leaves given by the last two weighing is only 9.
One the other hand, if we put 5 marbles (or more) in each pan, the opposite happens:
Everything is fine if the weighing is even (the odd marble is among the unweighed ones
and it's easy to pick in two weighing since there are 4 or less of these).
We are in trouble if the weighing is uneven since we have 10 (or more) possibilities
left for the odd marble and can't possibly make a 10-way decision tree in just
two weighing (again, the maximum is 9).
Interestingly, if you are given one extra regular marble (X),
it's possible to be 100% efficient in the first weighing (by involving 9 "unknown" marbles
instead of 8 or 10, as we tried unsuccessfully in the above) and, indeed, we can
detect an odd marble among 14 (ABCDEFGHIJKLMN) in just 3 weighings:
In the first weighing,
you compare ABCDE and FGHIX. If these sets are equal, you know the odd one is among
the 5 marbles JKLMN and can find out which it is with the 2 remaining weighings
(this is the same situation we had above with 13 marbles,
once 8 of them were ruled out).
Otherwise (say ABCDE < FGHIX),
you use the second weighing to compare ABF and CDG :
- If ABF=CDG, then the odd one is among EHI. 3rd weighing: H vs. I.
- If ABF<CDG, then the odd one is among ABG. 3rd weighing: A vs. B.
- If ABF>CDG, then the odd one is among FCD. 3rd weighing: C vs. D.
Note that, if you apply this new procedure to the case of 13 marbles
(ignoring the 14th marble N, which never gets weighed anyway),
you'll always be able to tell whether the odd marble is heavy or light.
It helps to have an extra marble X!
PS:
This was a difficult answer to give.
Many thanks to cibby (of S. Burlington, VT) for his kind words of appreciation,
within hours of the [12-marble] original posting...
(2001-08-20) General Counterfeit Penny Problem
How do you find a single counterfeit coin [either heavier or lighter than
a good one] among n coins in only k weighings on a two-pan balance?
First let's notice that all the information gathered at any point of the
weighing procedure can be summarized by putting all the coins in one of four bins
labeled E, G, L, or H (if E is not empty, H and L are).
After each weighing, the contents of the bins are "updated" to reflect
whatever new information has been obtained, so that:
- E contains e unweighed coins which could be good, heavy, or light.
- G contains g coins known to be good pennies.
- H contains the h coins which are known to be either good or heavy.
- L contains the m coins which are known to be either good or light.
If E is not empty, the argument given in the previous article tells you that there must be
at least (2e-1) leaves in the [rest of the] decision tree.
Similarly, if H and/or L are not empty, the minimum number of leaves is h+m
(in this case, the bad penny is determined to be heavy or light according to the label of
its original bin).
With k weighings, you have at most 3k different leaves in that decision tree.
With those remarks in mind, an optimal weighing procedure can be designed.
It is best to design the procedure assuming an extra good coin
(it turns out that we never need more than one) where we may achieve "100% efficiency"
at every step, as it was the case above with 14+1 coins and k=3 weighings...
(Other procedures will be fairly easy to derive from this one, as we shall see.)
If E is not empty (which implies that L and H are),
your first weighing involves x coins from E on the left pan and y coins on the right pan,
whereas z coins are left in the E bin (x+y+z=e).
Clearly, if you are allowed k weighings, you must make sure you can handle any
of the 3 outcomes of the first weighing in only k-1 weighings...
This means that 2z must be 3k-1+1 or less
(since you are left with z coins in E if the balancing comes out even),
whereas x+y must be 3k-1 or less
(since an uneven balance leaves you with x coins in L and y coins in H,
or the other way around). In the worst case
where 2e equals 3k+1, these inequalities must clearly be equalities.
The extra good coin may come in handy in this very first weighing (and only this one)
to even out the number of coins on each pan of the balance; after that we have a large
enough supply of known good coins...
(It's necessary to have the extra coin when x+y has to be the odd number
3k-1,
which is the case only when 2e is 3k+1.)
Similarly, if H and L are not empty (which implies that E is),
the bad penny may be found in k steps (or less) only if we proceed with a weighing
that always leaves a combined total of 3k-1 or less
in the H and L bins.
We start by weighing h1 coins from H and m1 coins from L against
h2 coins from H and m2 coins from L
(borrowing good coins from G to make the number of coins in each pan match, if needed).
We must do this so that
h0+m0, h1+m2 and h2+m1 are all 3k-1 or less.
When h+m is 3k or less, it's clearly always possible to do so!
(If we have a supply of good coins, there may be many ways to do this.)
That's essentially all there is to it! Read it carefully and you'll see that the
above is the backbone of a proof by induction that a counterfeit penny may be found
in k weighings among (3k+1)/2 coins or less,
if you are given an extra coin known to be good.
This corresponds to the last column of the Table below.
Not only that, but the above tells you exactly how to do it!
(It's also interesting to notice that only the sum h+m is relevant.
We need not insist on
keeping h and m nearly equal to design an optimal weighing procedure!)
To complete the Table below, only a few additional remarks are needed:
- First, if you have the extra good coin but insist on finding out if the counterfeit penny
is heavy or light, you can handle one less coin than if you don't require this.
(The "last coin" which is otherwise unweighed is thus left out.)
See the Table's third column.
- Second, the extra coin mat only be necessary in the first weighing,
since you always have a generous supply of known good coins after that.
As already observed above, we only need it when e=n is the maximum allowed value
of (3k+1)/2.
If e=n is just one one unit less than that, there's no need for the extra coin,
which is what is expressed by the second column of the Table.
- Finally, we may observe that in the inefficiency introduced by the lack of an
extra coin in this last case translates into the possibility of the bad penny being
left unweighted. With one less coin, that possibility is removed, as expressed by
the Table's first column.
Maximum Number of Coins Allowing Detection and/or Weight
Determination of a Counterfeit Penny in k Weighings of Less.
| k |
Without Extra Good Coin |
With Extra Good Coin |
| Find if Heavy/Light | Detection Only |
Find if Heavy/Light | Detection Only |
| 0 |
0 |
1 |
0 |
1 |
| 1 |
0 |
1 |
1 |
2 |
| 2 |
3 |
4 |
4 |
5 |
| 3 |
12 |
13 |
13 |
14 |
| 4 |
39 |
40 |
40 |
41 |
| 5 |
120 |
121 |
121 |
122 |
| 6 |
363 |
364 |
364 |
365 |
| 7 |
1092 |
1093 |
1093 |
1094 |
| 8 |
3279 |
3280 |
3280 |
3281 |
| 9 |
9840 |
9841 |
9841 |
9842 |
| 10 |
29523 |
29524 |
29524 |
29525 |
| k>0 |
(3k-3)/2 |
(3k-1)/2 |
(3k-1)/2 |
(3k+1)/2 |
Note that, without an extra marble, you can't do better with 1 weighing than with
none (k=0), namely just "detect" as bad the only penny you are presented with
(the general formulas do hold for k=1, but not for k=0 in the absence of an extra coin).
The case k=6 strongly suggests a nice (advanced) puzzle, presented next:
Gérard Michon
(2001-08-20)
Find-a-Birhday
John has 366 marbles marked with the days of the year.
All have the same weight except for the one corresponding to
his birthday...
If Mary knows John was born in 1966,
how can she find out his birthday in 6 weighings on a two-pan balance?
Since 1966 was not a leap year,
the marble marked "February 29" cannot be the one we seek,
It may thus be used as the so-called extra marble to find the special one among
the 365 others, in an optimal procedure (k = 6 weighings)
of the kind described in the previous article...
| k | N=3k |
|---|
| 0 | 1 |
| 1 | 3 |
| 2 | 9 |
| 3 | 27 |
| 4 | 81 |
| 5 | 243 |
| 6 | 729 |
| 7 | 2187 |
| 8 | 6561 |
| 9 | 19683 |
Napalm (2003-05-14)
Finding a Heavy Coin in k Weighings
You have 79 coins that are identical in all respects,
except that one is heavier than the others.
Can you find the heavy coin using only 4 weighings on a two-pan balance?
Well, you could even handle up to 81 coins this way.
The table at right shows the maximum number of coins N, among which a
single heavy coin can be found in k weighings...
This is about twice the number that could be handled if
the counterfeit coin wasn't known to be heavy or light,
as discussed in the previous articles
[see table].
When faced with N coins among which the heavy one is known to be,
what you do is simply divide N into three heaps that are as nearly equal as
possible. Two of these (at least) will contain the same number of coins
and can thus be compared using the balance.
If the weighing is uneven, you know that the bad coin is on the heavy side,
otherwise the bad coin must be in the heap that was left out.
Either way, you are face with a similar challenge, but with a number of coins
which is about one third as large as previously.
You do that until the size of the heap is reduced to 1.
If you start with 79 coins, the entire procedure is summarized by the following table:
Finding a heavy coin among 79, in 4 weighings :
| Weighing |
N | Left Pan | Right Pan | Not Weighed |
|---|
| 1st | 79 | 26 | 26 | 27 |
| 2nd | 27 | 9 | 9 | 9 |
| 26 | 9 | 9 | 8 |
| 3rd | 9 | 3 | 3 | 3 |
| 8 | 3 | 3 | 2 |
| 4th | 3 | 1 | 1 | 1 |
| 2 | 1 | 1 | 0 |
|
