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 theCounterfeit Coin Problem:Find a single counterfeit coin among 12 coins,knowing only that the counterfeit coin has a weightwhich differs from that of a good coin.You are only allowed 3 weighings on a two-pan balance and must also determineif 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 isin additionto the 13 or 14 "unknown" ones, but its presence makes the problemsimpler 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 your2nd 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 the3rd 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 weighingtells 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 whetherthe special marble is heavy or light, once you've determined which it is.
  Use the2nd weighing to compare ABE and CFL :
  • If ABE=CFL, you know the special marble is among DGH.You may use the3rd weighing to compare G and H :
    • If G=H, then D is the special marble.
    • If G and H are not equal, the special marbleis 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 the3rd weighing to find out.
    • ABCD>EFGH and ABE<CFL :
      Either E is light or C is heavy.
      Compare C and L in the3rd weighing to find out.
    • ABCD<EFGH and ABE<CFL :
      Either F is heavy or one of AB is light.
      Compare A and B in the3rd weighing to find out.
    • ABCD<EFGH and ABE>CFL :
      Either E is heavy or C is light.
      Compare C and L in the3rd 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 answerwas 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    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    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.

With 13 marbles (ABCDEFGHIJKLM), you may followexactly 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 youdon'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 ""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 isthe best we can do:Is there a totally different approach that would allow us to determine whetherthe odd marble is heavy or light with 13 marbles and/or todetect 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 of13 marbles and show that you cannot possiblyknow 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 just2 weighings, in case the first one comes out even. As each weighing has 3 possibleoutcomes, 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 thefirst 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 doesnot come out even, we are left with exactly 10possibilities: The odd marble could be any of the 10 that were put onthe balance (this first weighing does tell us, in each possible case, whetherthe 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 of14 marbles.Obviously, we can't find whether the odd marbleis 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 orlight, the weighing procedure will tell us in most cases: If the marble that'seventually found to be odd was involved in any weighing at all, we will knowif it's heavy of light.Now, remark that at each fork (ornode)of ourdecision tree there's at most one branch inwhich 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 ifall the weighings came out even.This corresponds to justone leaf of the decision tree!Therefore, any complete decision tree for n marbles would haveat mostone marble appearing as the answer only once in a leaf, whereas the (n-1) othersmust appear at least twice.In other words,any weighing procedure that can detect an odd object among nmust have at least (2n-1) leaves.If n is 14, this means 27 leaves, which is exactly what 3 weighingwould 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 only2, 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 outuneven (we finish the deal exactly as with 12 marbles, or even easier if we had less than4 marbles in each pan). However, we are in trouble if it comes out even, sincewe 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 thereforehave to build a decision tree with2n-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 onesand 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) possibilitiesleft for the odd marble and can't possibly make a 10-way decision tree in justtwo 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" marblesinstead of 8 or 10, as we tried unsuccessfully in the above) and, indeed, we candetect an odd marble among 14 (ABCDEFGHIJKLMN) in just 3 weighings:
   In thefirst weighing,you compare ABCDE and FGHIX. If these sets are equal, you know the odd one is amongthe 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 thesecond 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 of13 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)
How do you find a single counterfeit coin [either heavier or lighter thana 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 theweighing procedure can be summarized by putting all the coins in one of four binslabeled 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 reflectwhatever 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 beat 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 ofits 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 anextra 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 handleanyof the 3 outcomes of the first weighing in only k-1 weighings...This means that 2z must be3^k-1+1 or less(since you are left with z coins in E if the balancing comes out even),whereas x+y must be3^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 theworst casewhere 2e equals3^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 largeenough supply of known good coins...(It's necessary to have the extra coin when x+y has to be the odd number3^k-1,which is the case only when 2e is3^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 weighingthatalways leaves a combinedtotal of3^k-1 or lessin the H and L bins.We start by weighing h1 coins from H and m1 coins from L againsth2 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 thath0+m0, h1+m2 and h2+m1 are all3^k-1 or less.When h+m is3^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 theabove is the backbone of a proof by induction that a counterfeit penny may be foundin k weighings among(3^k+1)/2 coins or less,if you are given anextra 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 onkeeping 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 pennyis 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 youalways 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 valueof(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 anextra coin in this last case translates into the possibility of the bad penny beingleft unweighed. With one less coin, that possibility is removed, as expressed bythe 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
k0	(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 withnone (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 thecute presentation proposedbelow.

Let's just conclude with details about the maximalcase for 5 weighings  to present the above procedurein concrete terms:  With 120 marbles (without a reference marble)  we use thefirst weighingto compare two sets of 40 marbles.

If they're equal, we're faced with the task of findingwhich 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 startby putting 27 marbles on the scale, using one good marble for balance,so we'd be left with either 13 unweighed marbles or a situationsimilar to what's describedfurther down, with3 weighings available).

Otherwise, we have 40 known good marbles,a set L of 40 marbles known to be either good or light anda set H of 40 marbles known to be either good or heavy. With 4 weighings left, the above procedure requires thesecond 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 panagainst 13 from L and 13 from H, together with a known good marblefor 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 werein it, while L is reduced to the 13 of its elementswhich were on theright pan. 
• Otherwise, L now consists of its 14 elements to the left while Hconsists 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, thethird weighing (next) must leave no more than a totalof 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. Ourfourth weighing compares 2 from L and 1 from Hagainst 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 ourlast weighing, we compare one marble of L and one marble ofH to 2 good marbles from our huge stash.  We're done, aren't we?

FernandoA. Candeias (2009-10-17; e-mail) 
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 thingsfor 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 becauseit 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 thefirst weighing (it can be any  known good marble in subsequent weighings).

In spite of the simplicity of thegeneral recipe, whichis 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 columnare different and that every one of them verifiesthe 4 relations directly to its right (inequalities or equalities).

Gérard Michon(2001-08-20) 
John has 366 marbles marked with the days of the year. All have the same weight except for the one corresponding tohis 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-calledextra marble to find the special one amongthe 365 others, in anoptimal procedure (k = 6 weighings)of the kind described in the previous article...

(2009-10-20) 
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 corruptedin 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 usedto monitor and correct up to 13 trits of data. More generally,  k  uncorrupted ternary checksumscan 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 bemonitored and corrected by  k  checksum trits?

Well, we want to recover  3ⁿ  possible valid data statesfrom  3^n+k  possible codes among which at least3 (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 feweramong the  n+k  trits? Well, there are now at least  9 (n+k)(n+k-1)/2  codeswhich 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

Napalm (2003-05-14) 
You have 79 coins that are identical in all respects,except thatone 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 asingle heavy coin can be found in k weighings... This is abouttwice the number that could be handled ifthe counterfeit coin wasn'tknown 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 aspossible.  Two of these (at least) will contain the same number of coinsand 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 coinswhich 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