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 2022-10-23 Answered
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?
You can still ask an expert for help

Expert Community at Your Service

  • Live experts 24/7
  • Questions are typically answered in as fast as 30 minutes
  • Personalized clear answers
Learn more

Solve your problem for the price of one coffee

  • Available 24/7
  • Math expert for every subject
  • Pay only if we can solve it
Ask Question

Answers (2)

ohhappyday890b
Answered 2022-10-24 Author has 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.
Did you like this example?
Subscribe for all access
Ryder Ferguson
Answered 2022-10-25 Author has 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 }.
Did you like this example?
Subscribe for all access

Expert Community at Your Service

  • Live experts 24/7
  • Questions are typically answered in as fast as 30 minutes
  • Personalized clear answers
Learn more

You might be interested in

asked 2021-09-07
A city water department is proposing the construction of a new water pipe, as shown. The new pipe will be perpendicular to the old pipe. Write an equation that represents the new pipe.
asked 2021-09-17
The function y=3.5x+2.8 represents the cost y (in dollars) of a taxi ride of x miles.
a. Identify the independent and dependent variables.
b. You have enough money to travel at most 20 miles in the taxi. Find the domain and range of the function.
asked 2021-09-21
The solution of the given equation.
5(1.3)x+4=104
asked 2021-09-27
What is the first step when modeling linear relationships given limited information?
asked 2021-09-12
Modeling situations as functions is common. Describe whether each description represents a function. Explain.
a. The input is a day of the year. The output is the average temperature in Barcelona on that day.
b. The input is speed of a car. The output is the time it takes for a car moving constantly at that speed to travel 100 miles.
c. The input is a positive number. The output is a number whose absolute value is the input.
d. The input is a year. The output is the population of the United States during that year.
asked 2021-06-22
Describe mathematical modeling in you r own words.
asked 2021-01-27
Marcus rowed 20 miles downstream in 2 hours. The trip back, however, took him 4 hours. Find the rate that Marcus rows in still water and the rate of the current. If x is Marcuss

New questions