dgc@ucla-cs.UUCP (04/14/85)
-------
Here's a different kind of coin weighing puzzle:
Suppose that all coins come in one of two different weights, and that
you know what these weights are. For example, each coin might weigh
5 grams or 10 grams. Coins are indistinguishable, except by their
weight. The coins with the lower weight are called "light" and the
others "heavy".
You are given n coins. Your problem (S. Y. C. T. A. I.) is to obtain
each of the coins' weights in the least number of weighings using a
"calibrated" scale which gives you the total weight of the coins you
are weighing, and exactly. A "weighing" consists of taking some of the
coins, and obtaining the total weight of the selected coins.
As an example, the following scheme shows that you can determine the
weights of each of 4 coins in a total 3 weighings.
The coins are numbered from 1 to 4 and their weights are, respectively,
x , x , x , x .
1 2 3 4
Then in 3 weighings determine the following numbers:
x + x + x + x
1 2 3 4
x + x
2 3
x + x
1 3
This means that in the first weighing all four coins are weighed
together, in the second, coins 2 and 3 are weighed, etc.
To see that this works, first note that each weighing really tells you
how many of the light coins and how many of the heavy coins you weighed,
so that you might as well assume that the weights of the coins are
really 0 and 1.
Then the sum of the results of all of the weighings is
2x + 2x + 2x + x
1 2 3 4
Under the assumption above, this must be a non-negative integer; if it
is odd, then x must be 1, otherwise it must be 0.
4
Having determined the weight of the 4th coin, the weights of the other
coins can now be easily determined. (It amounts to solving 3 equations
in 3 unknowns.)
By using this scheme twice, you can determine the weights of 8 coins in
6 weighings.
A. Can you determine the weights of 8 coins in 5 weighings?
B. In general, what is the best you can do in m weighings?
David G. Cantor
ARPA: dgc@ucla-locus.arpa
UUCP: ...!{ihnp4, randvax, sdcrdcf, ucbvax}!ucla-cs!dgc