This is a intriguing problem, usually stated in terms such as the following:

You are given 12 coins, labeled, but otherwise indistinguishable in appearance, and told that all but one of them (the 'counterfeit', unidentified) are identical in weight.

You are provided with a balance which you may use to compare the weights of equal numbers (up to half the total) of the coins on each side, sufficiently accurate to detect the imbalance which occurs only when the counterfeit participates in a weighing.

Your problem is to identify the counterfeit coin, and also to determine whether it is heavier or lighter than the others, in not more than 3 weighings.

In general, it can be demonstrated that $$n \in \mathbb{N}_0$$ weighings are sufficient to identify the counterfeit among a set of at most $$\frac{3^n - 3}{2}$$ coins.

Assignment

The result of any sequence of $$n$$ weighings can be represented as an $$n$$-digit ternary (base 3) integer (str) that only contains the digits 0, 1 and 2. The consecutive digits (from left to right) correspond to successive weighings, each digit having the following significance:

• 0: no imbalance detected (i.e. counterfeit absent from weighing)

• 1: left side heavier

• 2: right side heavier

Such ternary integers are here referred to as weighing patterns, or simply patterns. Since the counterfeit does not necessarily participate in the first weighing, leading zeroes in patterns are significant and must not be suppressed.

A weighing plan gives instructions for $$n$$ weighings that need to be performed to identify the counterfeit among a set of $$m$$ coins (with $$m \leq \frac{3^n - 3}{2}$$). This is done by assigning each coin a unique pattern of $$n$$ weighings (how is not important for this assignment). For example, if each of the 12 coins from the original problem is labeled with a unique letter, this might be the weighing plan for 12 coins:

For the $$i$$-th weighing ($$i = 0, 1, \ldots, n - 1$$), the $$i$$-th digit (from the left) of each pattern indicates how the corresponding coin participates in the weighing:

• 0: coin does not participate

• 1: coin is placed on the left side of the balance

• 2: coin is placed on the right side of the balance

Both sides of the balance always have the same number of coins, and each coin is weighed at least once (in other words, the pattern 00…0 does not appear in the weighing plan). For example, the weighing plan for 12 coins indicates that the following weighings must be performed:

To identify the counterfeit, the results of the successive weighings must be listed in the form of a "pattern": the first digit indicates the result of first weighing, the second digit indicates the result of the second weighing, and so on. The digits have the following significance:

• 0: balanced weighing (counterfeit did not participate)

• 1: coins on the left weighed more than those on the right

• 2: coins on the left weighed less than those on the right

Now there are two possibilities:

• the resultant pattern corresponds to a single coin in the weighing plan: that is the counterfeit that weighs heavier than the other coins

• the converse of the resultant pattern corresponds to a single coin in the weighing plan: that is the counterfeit that weighs lighter than the other coins

The converse of a pattern $$p$$ is defined as the pattern obtained by replacing each occurrence of the digit 2 by the digit 1 in pattern $$p$$, and replacing each occurrence of the digit 1 by the digit 2.

Your task:

• Write a function converse that takes a pattern (str). The function must return the converse (str) of the given pattern.

• Write a function balance that takes three arguments: i) a collection (list, tuple or set) containing the labels (str) of the coins that are placed at the left side of the balance, ii) a collection (list, tuple or set) containing the labels (str) of the coins that are placed at the right side of the balance, and iii) the label (str) of the counterfeit. The function may assume that both collections contain the same number of labels, and that no label appears more than once. The function also has an optional parameter heavier that may take a Boolean value (bool) that indicates if the counterfeit is lighter (False) or heavier (True) than the other coins (default value: False). The function must return the digit (int; 0, 1 or 2) that describes the state of the balance upon weighing both collections of coins.

• Write a function labels that takes the location (str) of a text file containing the description of a weighing plan. Each line of the file must contain the unique label of a coin, followed by a comma (,) and the pattern assigned to the coin in the weighing plan. The function must return a dictionary (dict) whose keys are the individual patterns (str) in the given text file. The dictionary must map each pattern onto the label (str) of the corresponding coin.

• Write a function weighing_plan that takes a dictionary (dict) for a weighing plan as returned by the function labels. The function must return a list containing the successive weighings ($$i = 0, 1, \ldots, n - 1$$) that must be performed according to the given weighing plan. Each weighing is represented as a tuple with two elements: i) the set of labels (str) of all coins that are placed at the left side of the balance during the $$i$$-th weighing and ii) the set of labels (str) of all coins that are placed at the right side of the balance during the $$i$$-th weighing.

• Write a function weighing_pattern that takes two arguments: i) a dictionary (dict) for a weighing plan as returned by the function labels and ii) the label (str) of the counterfeit. The function also has an optional parameter heavier that may take a Boolean value (bool) that indicates if the counterfeit is lighter (False) or heavier (True) than the other coins (default value: False). The function must return string (str) that lists the results of the successive weighings in the form of a "pattern", if the given weighing plan is performed with the given counterfeit.

• Write a function counterfeit that takes two arguments: i) a dictionary (dict) for a weighing plan as returned by the function labels and ii) a string (str) that lists the results of the successive weighings in the form of a "pattern", if the given weighing plan is performed. The function must return a tuple with two elements: i) the label (str) of the counterfeit and ii) a Boolean value (bool) that indicates if the counterfeit is lighter (False) or heavier (True) than the other coins.

Example

In the following interactive session, we assume the text file plan.txt¹ to be located in the current directory.

>>> converse('102')
'201'
>>> converse('200')
'100'

>>> balance({'A', 'B', 'C', 'D'}, {'E', 'F', 'G', 'H'}, 'F')
1
>>> balance({'A', 'B', 'C', 'D'}, {'E', 'F', 'G', 'H'}, 'F', True)
2
>>> balance({'A', 'J', 'K', 'L'}, {'B', 'C', 'D', 'E'}, 'F')
0
>>> balance({'A', 'J', 'K', 'L'}, {'B', 'C', 'D', 'E'}, 'F', True)
0
>>> balance({'C', 'F', 'I', 'L'}, {'A', 'D', 'G', 'J'}, 'F')
2
>>> balance({'C', 'F', 'I', 'L'}, {'A', 'D', 'G', 'J'}, 'F', heavier=True)
1

>>> plan = labels('plan.txt2')
>>> plan['121']
'C'
>>> plan['202']
'G'
>>> plan['011']
'L'

>>> weighing = weighing_plan(plan)
>>> weighing[0]
({'A', 'B', 'C', 'D'}, {'E', 'F', 'G', 'H'})
>>> weighing[1]
({'A', 'J', 'K', 'L'}, {'B', 'C', 'D', 'E'})
>>> weighing[2]
({'C', 'F', 'I', 'L'}, {'A', 'D', 'G', 'J'})

>>> weighing_pattern(plan, 'F')
'102'
>>> weighing_pattern(plan, 'F', True)
'201'
>>> weighing_pattern(plan, 'H', heavier=False)
'100'
>>> weighing_pattern(plan, 'H', heavier=True)
'200'

>>> counterfeit(plan, '102')
('F', False)
>>> counterfeit(plan, '200')
('H', True)

Resources

• Smith C (2005). The twelve coin problem. The Mathematical Gazette 89(515), 280–281. ³

• Wetherfield M (2005). The generalised coin weighing problem. The Mathematical Gazette 89(515), 275–279 ⁴.