Modeling the coin weighting problem. Suppose we have n coins with weights 0 or 1 and a scale for weighting them. We would like to determine the weight of each coin by minimizing the number of weightings.
faois3nh
Answered question
2022-10-23
Modeling the coin weighting problem Suppose we have n coins with weights 0 or 1 and a scale for weighting them. We would like to determine the weight of each coin by minimizing the number of weightings. The book that I am reading states that the above problem can be modeled in the following way. We say that the subsets of {1,…,n} are determing if any can be uniquely determined by the cardinalities for . The minimum number of weightings is then equivalent to the least m for which a determing sequence of sets exists. My question is. How exactly does this reduce to the coin weighting problem?
Answer & Explanation
ohhappyday890b
Beginner2022-10-24Added 12 answers
Step 1 Let T be the set of coins with weight 1. Then, the weight of the subset is precisely . Step 2 If we weigh each , we will be able to recover T.
Ryder Ferguson
Beginner2022-10-25Added 3 answers
Step 1 Let the coins be . Let T be the set of coins of weight 1, and let
the set of indices of those coins. For let , and let be the total weight of the coins in . Since each coin has weight 1 or 0, is the number of coins in of weight 1, which is . Thus,
Step 2 If you weigh each of the sets , those m weighings will give you the numbers for . If the sets are determining, those m numbers uniquely determine the set T, from which you immediately get .