Monday Math 8: Twelve Coins

Twelve Coins

This is a classic problem: you have twelve coins identical in shape and appearance. One of them is a counterfit, and has a slightly different weight; it is either heavier or lighter, but you don’t know which. Given only a balance scale, can you find the false coin, and whether it is heavier or lighter, in only three weighings?

Given the general set up, you can find the false coin amongst total coins in n weighings (with n≥2). This is the n=3 case.

First, let us consider the example of only 3 coins (the n=2 case). We will label the three coins X, Y, Z. There are three positions a coin can be placed:
1) on the left basket of the scale
2) on the right basket of the scale
3) off the scale
Now, let us first weigh X versus Y. Indicating the contents of positions 1, 2, 3 in that order, this is (X,Y,Z). For our second weighing, let us weigh Y versus Z. This can be represented by a cyclic permutation (or “rotation”) of our previous state: (Y,Z,X).
Note that at least one of these weighings will contain the false coin and will not balance. We examine the possibilities:
I. X vs Y balances, Y vs Z does not
X balancing Y means they are the real coins, and thus Z is counterfit. Its weighing versus Y tells you if it is heavy or light.
II. X vs Y does not balance, Y vs Z does
Here, the balancing of Y vs Z means X is counterfit; it’s weighing against Y thus tells us if it is heavy or light.
III. Both weighings fail to balance
This means the fake is in both weighings: it is thus Y. Either weighing can tell you if it is heavy or light.

Now, for the twelve coin problem. We divide the coins into two sets: a ‘large’ set of nine, and a ‘small’ set of three. We then divide the large set into three sets of three, which we shall call X,Y,Z; and call the three coins of the small set x,y,z.

Now, for our first weighing, we measure X+x versus Y+y: (Xx,Yy,Zz).
Next, we cyclicly permute the large set groups, weighing Y+x versus Z+y: (Yx,Zy,Xz).
Let us consider the possibilities:
I. Both balance.
Then the false coin could have been in none of the weighings, and is thus the coin z. A third weighing, of z versus any other coin, tells us if it is heavy or light.
II. (Xx,Yy,Zz) balances, (Yx,Zy,Xz) does not.
This tells us the counterfit coin is in Z, and the second weighing tells us if it is heavy or light. We then weigh any two of the three coins in Z against each other: if they balance, the third is the fake. If they don’t balance, we know which of the two is the fake as we know if the fake is heavy or light.
III. (Xx,Yy,Zz) doesn’t balance, (Yx,Zy,Xz) does.
This tells us the counterfit coin is in X, and the first weighing tells us if it is heavy or light. Then we do for X in this case as we do for Z in case II to find the fake.
IV. (Xx,Yy,Zz) and (Yx,Zy,Xz) are both unbalanced in the same direction.
This tells us either x or y is the fake. Weigh x versus z. If they babance, y is the fake, and the first two weighings tell us if y is light or heavy. If x and z don’t balance, x is the fake, and any of the three weighings will indicate if it is heavy or light.
V. (Xx,Yy,Zz) and (Yx,Zy,Xz) are both unbalanced in opposite directions.
This is why the cyclic permutation is important: to distinguish this case from IV. Here, we know that the fake is in Y, and if it is heavy or light. To find the fake, we proceed as in case II or case III.

This method can also be analogized to the general case of total coins in n weighings, which I will leave as an exercise to you, the reader.

Advertisements

Tags: , ,

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: