Related Links (Outside this Site)

bobbejones (2001-04-12)
You have 12 marbles, one of them is either heavier or lighter than the others. How can you determine the odd marble in  only  three weighs on a balance scale?

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.

On 2001-04-13, Cibby  (of S. Burlington, VT)  wrote a few kind words of appreciation, a few hours after the above answer was posted  (which was tough to come up with in a short time).  We thank him very much for that.

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 3²=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=3³ ), 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 :

• If ABF=CDG, then the odd one is in EHI.  3rd weighing: H vs. I.
• If ABF<CDG, then the odd one is in ABG.  3rd weighing: A vs. B.
• If ABF>CDG, then the odd one is in 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!

(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 3^k 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 3^k-1+1 or less (since you are left with z coins in E if the balancing comes out even), whereas x+y must be 3^k-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 3^k+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 3^k-1, which is the case only when 2e is 3^k+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 3^k-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 3^k-1 or less. When h+m is 3^k 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 (3^k+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 (3^k+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 unweighed. 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 or 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, 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.

• If the weighing is even, we're faced with 13 marbles in L and 14 in H.
• If the left pan is heavy, H is now reduced to its 13 elements which were in it, while L is reduced to the 13 of its elements which were on the right pan. 
• Otherwise, L now consists of its 14 elements to the left while H consists of its 13 elements to the right.

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?

Fernando A. Candeias (2009-10-17; e-mail)   41 marbles in 4 weighings...
I am 84 years old.  Explicit tables for 41 marbles might be helpful to me.

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

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

(2009-10-20)   Ternary Error-Correcting Codes
Putting the  Counterfeit Penny  puzzle to work...

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  (3^k-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  3ⁿ  possible valid data states from  3^n+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   ≤   3^k-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   ≤   3^k-2

The general formula for correcting at most  q  errors is   C(n+k,q) ≤ 3^k-q

Wikipedia :   Shannon's Theorem   |   Error Correction Codes

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 [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 :

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