Counterfeit Coin

The problem

Given a set of coins among which there is a counterfeit coin of a different weight, find this counterfeit coin using ordinary balance scales, with the minimum number of weighings possible, and indicate whether it weighs less or more than the rest. The best known specific case is that of twelve coins and three weighings.

Theoretical bases

The work is based on the evident analogy between the optimum codes capable of detecting and correcting 1 error in a message of n digits and the best procedure for finding 1 counterfeit coin and establishing whether it weights more or less in a set of n coins.

The Hamming code is capable of detecting and correcting 1 error in a message of n digits with the minimum redundancy required by Information Theory.

In order to implement a Hamming code, a test matrix (or table of numbers) must be built. This matrix will have as many rows as redundant equations and as many linearly independent columns as digits in the message.

Similarly, the procedure for performing the weighings can also be expressed as a table of numbers in which each row indicates which coins should appear in each weighing and each column indicates a coin.

It can be concluded that the test matrix of the Hamming codes is the table of numbers expressing the procedure for performing the weighings.

Procedure

Since the counterfeit coin may weigh less or more than the rest, we have two possible values which we will call 1 and 2. The value 0 is reserved for the case in which the coin is not counterfeit. Just as a balance scales may acquire three different positions, balanced, tilted leftwards and titled rightwards, we will again have three possible values which we will again call 0, 1 and 2.

In accordance with the above, we must build a table of numbers using the values 0, 1 and 2, i.e. in base 3. In other words, we must design a Hamming code in base 3. The table of numbers must have as many rows as weighings. For example, if we assume three weighings, it must have three rows. The numbers which appear in the table must be written with the digits 0, 1 and 2, i.e. in base 3. These three-digit numbers will be the 3³ = 27 following numbers: 000, 001, 002, 010, 011, 012, 020, 021, 022, 100, 101, 102, 110, 111, 112, 120, 121, 122, 200, 201, 202, 210, 211, 212, 220, 221, 222.

Of these, it is necessary to eliminate 000, which would indicate that the coin does not appear in any weighing , leaving a total of 3³-1 different numbers, and if each represents a different coin, it is necessary to avoid the sum of any two vectors or columns being nil, as in columns (0, 1, 2) and (0, 2, 1). This difficulty can be overlooked if all the first elements other than zero in each of the columns of the test matrix H is worth 1. Thus, no pair of columns will be linearly dependent upon another and this matrix is valid for building codes able to detect and correct an error.

Of the total number of columns other than 0 that can be written with x rows in base 3; 3^x 1, it will be necessary to choose only the fraction 1/(3-1) whose first non-nil element is equal to 1. The maximum column number that can be obtained thus is (3^x-1)/2 and this number must be the same or higher than that of coins (3^x-1)/2³n.

Accordingly, for n=12 coins, the number of weighings or linear equations or rows of the matrix H must be equal to or higher than 3. The test matrix for x=3 is:

   1  2  3  4  5  6  7  8  9  10  11  12  13
   0  0  0  0  1  1  1  1  1   1   1   1   1 s1
   0  1  1  1  0  0  0  1  1   1   2   2   2 s2
   1  0  1  2  0  1  2  0  1   2   0   1   2 s3

It might sometimes be preferable to build a more complex test matrix in exchange for the weighings being easier. Here, there is an additional condition that the test matrix must have the same number of 0s, 1s and 2s in each row in order to be able to directly assign the coins to a particular side of the scales.

For each row of this matrix to have the same number of 0s, 1s and 2s, the following property will be used: if any vector of the matrix is multiplied by 2 module 3, the sum of any pair of vectors or columns continues to be non-nil .

The first row of the matrix contains four 0s, eight 1s and no 2s. In order for it to have four 1s and four 2s, we will multiply the four vectors and columns on the right side, i.e. those corresponding to coins 9, 10, 11, 12 by 2 module 3 (this operation transforms 1s into 2s, 2s into 1s and maintains the 0 values) the matrix thereby having the same number of 0s, 1s and 2s in the first row:

   1  2  3  4  5  6  7  8  9  10  11  12
   0  0  0  0  1  1  1  1  2   2   2   2
   0  1  1  1  0  0  0  1  2   2   1   1
   1  0  1  2  0  1  2  0  2   1   0   2

The second row now has four 0s, six 1s and two 2s. In order for it to contain four 2s, we will multiply by 2 module 3 the two vectors with the highest values (furthest to the right) which contain 1 in row 2 and 0 in row 1. These vectors will be columns 3 and 4. The matrix will therefore be as follows:

   1  2  3  4  5  6  7  8  9  10  11  12
   0  0  0  0  1  1  1  1  2   2   2   2 
   0  1  2  2  0  0  0  1  2   2   1   1 
   1  0  2  1  0  1  2  0  2   1   0   2 

The matrix thereby has the same number (four) of 0s, 1s and 2s in each row. In addition to indicating which coins must appear in each weighing, this matrix identifies with the value 1 those coins which should appear, for example, on the left side of the scales and with a 2 those which must appear on the right and with 0 those which do not intervene in the weighing. The following weighings can therefore be deduced:

   s1   5,  6,   7,   8  <>  9,  10,  11,  12
   s2   2,  8,  11,  12  <>  3,   4,   9,  10
   s3   1,  4,   6,  10  <>  3,   7,   9,  12

The result of the weighings s1, s2, s3 obtained by assigning 1 to the left-hand tilt, 0 for balance and 2 for the right-hand tilt will serve to identify in the matrix which is the counterfeit coin and in this case that it is heavier.

If s1, s2, s3, cannot be found in the matrix, the vector s1/2, s1/2, s1/2, will be obtained (this operation is equivalent to replacing value 1 with 2 and 2 with 1 and 0 remaining unchanged) the coin will be identified in the matrix and in this case it is lighter.

Example 1:

   First weighing:   moving to the right   s1=2
   Second weighing:  moving to the right   s2=2
   Third weighing:   moving to the right   s3=2

The counterfeit coin is 9 and it is heavier.

Example 2:

   First weighing is balance      s1=0
   Second weighing is balance     s2=0
   Third weighing to the right    s3=2

The counterfeit coin is [s1=0/2=0, s2=0/2=0, s3=2/2=1] 1 and lighter.

Generalization

In the information contained in the paper of the same title.is included as an example of how to build the matrix for both 12 coins with three weighings and 39 coins with 4 weighings. Consequently, anyone interested can find the procedure for the case of 120 coins and 4 weighings, 363 coins and 6 weighings, and 1,092 coins and 7 weighings, etc. since there is a perfect code for all of these instances.