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...
First, let's deal with 12 marbles, call them ABCDEFGHIJKL:
First weighing: Compare ABCD and EFGH.
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.
On 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 :
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!
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:
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:
Maximum Number of Coins Allowing Detection and/or Weight
Determination of a Counterfeit Penny in k Weighings or Less.
Note that, without an extra marble, we can't do better with 1 weighing than with none (k=0), namely just "detect" as bad the only penny we 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 suggests the cute presentation proposed below.
Let's just conclude with details about the maximal case for 5 weighings to present the above procedure in concrete terms: With 120 marbles (without a reference marble) we use the first weighing to compare two sets of 40 marbles.
If they're equal, we're faced with the task of finding which of the 40 unweighed marbles is odd and whether it's heavy or light, but we can do so using just one of our 80 known good marbles (we'd start by putting 27 marbles on the scale, using one good marble for balance, so we'd be left with either 13 unweighed marbles or a situation similar to what's described further down, with 3 weighings available).
Otherwise, we have 40 known good marbles, a set L of 40 marbles known to be either good or light and a set H of 40 marbles known to be either good or heavy. With 4 weighings left, the above procedure requires the second weighing (next) to leave a total of at most 27 marbles in L and H (down from the current 80). We must thus put at least 53 marbles from H and L on the scale. (Because this is a tight case, we'd also be in trouble if we put more than 54.) So, let's compare 14 marbles from L and 13 from H in the left pan against 13 from L and 13 from H, together with a known good marble for proper balance.
Let's consider only the last case, since the others are not more complicated:
We now have 14 marbles in L and 13 in H, with 3 weighings available. So, the third weighing (next) must leave no more than a total of 9 marbles in L and H. This can be achieved by putting 18 marbles on the scale, comparing 5 from L and 4 from H against 5 from L and 4 from H . Every outcome leaves 5 marbles in L and 4 in H, or the other way around (we'll assume the former case is true).
9 marbles remain (5 in L, 4 in H). We have to weigh 6 of them. Our fourth weighing compares 2 from L and 1 from H against 2 from L and 1 from H.
This leaves 2 marbles in L and 1 in H, or the other way around (if the weighing came out even). In our last weighing, we compare one marble of L and one marble of H to 2 good marbles from our huge stash. We're done, aren't we?
I hope that, 30 years from now, when I am your age (God willing) I shall still feel the urge to investigate new useless things for the heck of it! Meanwhile, allow me to praise this youthful attitude of yours. Way to go!
Although I am not sure whether another lengthy table can help, I'll bite the bullet...
Among 41 marbles, you can always detect a single bad marble in 4 weighings. However, in the first case listed below (where the odd marble is the 41-st one, labeled by the lowercase letter "o") you won't be able to tell whether that bad marble is heavy or light because it never touched the balance at all (in that case, the 4 weighings only prove that all the other marbles were the same).
There are 81 possible results (note that this is a power of 3, because we are faced with extremal circumstances here). The name of the bad marble appears in the final column. The symbol "*" denotes the "extra" good marble you need for the first weighing (it can be any known good marble in subsequent weighings).
In spite of the simplicity of the general recipe, which is best applied directly (using sorting bins, as prescribed) the above table is quite tedious to build, on account of its size. Its consistency can be established by checking that all 81 entries of the last column are different and that every one of them verifies the 4 relations directly to its right (inequalities or equalities).
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...
In all of the above, we may view each coin or marble as a digital trit (ternary digit) which may have been corrupted in one of two ways, making the assumption that at most one of those trits could have been corrupted. Each weighing is just a ternary checksum (its result is itself a trit). The checksums can be used to restore corrupted data!
As the above may suggest, 3 (uncorrupted) checksums can be used to monitor and correct up to 13 trits of data. More generally, k uncorrupted ternary checksums can monitor and correct up to (3k-1)/2 trits of data.
If the results of checksums are not more reliable than the data trits, then, surely, only a lesser amount of data can be reliably dealt with: Assuming that there's at most one error among data or checksums, what is the maximum number of data trits which can be monitored and corrected by k checksum trits?
Well, we want to recover 3n possible valid data states from 3n+k possible codes among which at least 3 (n+k) are mapped to the same valid data. Regardless of practical decoding details, this is possible if and only if:
n ≤ 3k-1 - k
What is needed to deal with 2 errors of fewer among the n+k trits? Well, there are now at least 9 (n+k)(n+k-1)/2 codes which must map to the same valid piece of data and, so, we must have:
(n+k)(n+k-1) / 2 ≤ 3k-2
The general formula for correcting at most q errors is C(n+k,q) ≤ 3k-q
Wikipedia : Shannon's Theorem | Error Correction Codes
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 [cf. table].
When faced with N coins among which the heavy one is known to be, what we 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 we can compare them with our balance. If the weighing is uneven, we 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, we're faced with a similar challenge, but with a number of coins which is about one third as large as previously. We iterate the process until the size of the heap is reduced to 1. If we start with 79 coins, the entire procedure is summarized by the following table:
Finding a heavy coin among 79, in 4 weighings :