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

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 S 1 , , S m of {1,…,n} are determing if any T { 1 , , n } can be uniquely determined by the cardinalities | S i T | for 1 i m .. 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

ohhappyday890b

Beginner2022-10-24Added 12 answers

Step 1
Let T be the set of coins with weight 1. Then, the weight of the subset S i is precisely | S i T | .
Step 2
If we weigh each S i , we will be able to recover T.
Ryder Ferguson

Ryder Ferguson

Beginner2022-10-25Added 3 answers

Step 1
Let the coins be C 1 , , C n . Let T be the set of coins of weight 1, and let
T = { k { 1 , , n } : C k T } ,
the set of indices of those coins. For k = 1 , , m let S k = { C k : k S k }, and let w k be the total weight of the coins in S k . Since each coin has weight 1 or 0, w k is the number of coins in S k of weight 1, which is | S k T | . Thus,
w k = | S k T | = | S k T | .
Step 2
If you weigh each of the sets S k , those m weighings will give you the numbers | S k T | for k = 1 , , m. If the sets S k are determining, those m numbers uniquely determine the set T, from which you immediately get T = { C k : k T }.

Do you have a similar question?

Recalculate according to your conditions!

Ask your question.
Get an expert answer.

Let our experts help you. Answer in as fast as 15 minutes.

Didn't find what you were looking for?