Problem
There are \(N\) bags, each containing sufficiently many coins. All but one bag contain identical “normal” coins, but in one bag all the coins are counterfeit. The weight of a normal coin is known, and it is known that a false coin is one gram lighter than a normal coin. It if required to find a bag with false coins by a single weighing on scales with a set of weights.
Solution
Let the bags be numbered consecutively and from each bag a number of coins equal to the number on the bag is taken. The total weight of all the coins selected in this way will “fall short of” the weight of the same number of normal coins by a number of grams equal to the number on precisely that bag containing the false coins.
Example
If the normal coin is \(5\) grams and there are \(10\) bags with the \(8^{th}\) bag having counterfeit coins. If we select \(i\) coins from the \(i^{th}\) bag, the total weight of all the coins selected is \(5\cdot 1 + 5\cdot 2 + \dots + 4 \cdot 8 + 5 \cdot 9 + 5 \cdot 10 = 267\). Had all the bags contained normal coins the total weight of the coins would have been \(275\). Therefore by measuring the shortfall \(275-267=8\), we can measure the bag containing the counterfeit coins.
Generalization - problem of bags with several kinds of coins
Suppose that there are \(N\) bags, each containing sufficiently many coins. There are coins of various kinds but in a particular bag are all of a single kind. The number of bags with coins of a given kind is arbitrary and unknown. Two coins of different kinds differ in weight by an integral number of grams. The set of all possible weights in known. It is required to determine the kind of coins in each bag by means of a single weighing on scales with a set of weights.
Solution
Let the bags be numbered consecutively from \(0\) to \(N-1\). Denote the weight of the lightest coin by \(m\) and the weight of the heaviest coin by \(m+k-1\). Suppose that the bag with number \(j\) contains coins of weight \(m+\Delta_j\), so that \(\Delta_j\) determines the kind of coins in the \(j^{th}\) bag. Depending on the kind of coins, the quantities \(\Delta_j\) can take (integer) values \(0,1,2,\dots, k-1\).
From the bag with number \(j\), we now take \(k^j\) coins, that is, \(1\) from the first bag, \(k\) from the second bag, \(\dots\), \(k^{N-1}\) from the last bag. The total number of coins taken is
\[ M = \sum_{j=0}^{N-1}k^j = 1 + k + k^2 +\dots + k^{N-1} = \frac{k^N-1}{k-1}. \]
Their total weight \(S\) on the scales is
\[ M = \sum_{j=0}^{N-1} (m+Δ_j) k^j = m \sum_{j=0}^{N-1} k^j + \sum_{j=0}^{N-1} \Delta_j k^j = m.M + \sum_{j=0}^{N-1}\Delta_j k^j. \]
Since \(\Delta_j\) is always \(<k\), the second sum
\[ \Delta = \sum_{j=0}^{N-1} \Delta_jk^j = \Delta_0 + \Delta_1k + \Delta_2k^2 + \dots + \Delta_{N-1}k^{N-1} \]
on the right-hand side is the translation of the number \(\Delta\) from the decimal number system (in which the weights are given) into the number system with base \(k\). In this system \(\Delta\) is written as a number with the following sequence of digits:
\[ \Delta \rightarrow \overline{\Delta_{N-1}\Delta_{N-2}\cdots \Delta_{1}\Delta_{0}} \]
We see that the digits in this expression indicate the kinds of coins in the sequence of bags, taken in the reverse order.
Accordingly, from the total weight \(S\) of all the \(M\) coins selected we subtract the weight \(Mm\) of the same number of coins of the lightest kind and then represent the difference \(\Delta = S- mM\) in the number system with base \(k\) (we decompose into powers of \(k\), beginning with the highest power). The \(j^{th}\) digit from the end (counting from zero) indicates the kind of \(\Delta_j\) coins in the bag with number \(j\).
Example
| 4 | 3 | 2 | 1 | 0 | number j on bag |
|---|---|---|---|---|---|
| 11 g | 13g | 9g | 13g | 9g | weight m+\(\Delta_j\) of a coin |
| 2 | 4 | 0 | 4 | 0 | kind \(\Delta_j\) of coin |
| 625 | 125 | 25 | 5 | 1 | number \(k^j\) of coins selected |
In this case \(k=5\) and the numbers of coins correspond to powers of \(5\), as shown in the last row of the table.We select \(781\) coins in all. Their total weight on the scales is \(8799\). Subtracting \(M.m = 7029\), we get \(\Delta = 1770\).
Expressing \(\Delta\) as a number in base \(5\),
\[ \Delta = 2\cdot5^4 + 4\cdot5^3 + 0\cdot5^2 + 4\cdot5^1 + 0\cdot5^0, \]
we get the number \(\overline{24040}\), and the sequence of digits coincide with the original sequence of kinds given in the table.
Code to print the kind of coins in each bag
def base10toN(num, base):
"""Change ``num'' to given base
Upto base 36 is supported."""
converted_string, modstring = "", ""
currentnum = num
if not 1 < base < 37:
raise ValueError("base must be between 2 and 36")
if not num:
return '0'
while currentnum:
mod = currentnum % base
currentnum = currentnum // base
converted_string = chr(48 + mod + 7*(mod > 10)) + converted_string
return converted_string
"""Inputs"""
num_bags = 5
min_weight = 9
max_weight = 13
total_weight = 8799
base = max_weight-min_weight + 1
M = sum([base**i for i in range(num_bags)])
print(base10toN(total_weight - min_weight*M, base))References
Kvant Selecta Combinatorics 1, Serge Tabachnikov