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^{2}=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^{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 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 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

(3^{k}-3)/2

(3^{k}-1)/2

(3^{k}-1)/2

(3^{k}+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^{n} 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

k

1

2

3

4

5

6

7

8

9

10

11

12

13

n

0

1

6

23

76

237

722

2179

6552

19673

59038

177135

531428

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}

k

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

n

0

0

0

0

2

7

15

30

57

105

187

332

582

1017

1771

3077

5340

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

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: