# 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.

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},\dots ,{S}_{m}$ of {1,…,n} are determing if any $T\subseteq \left\{1,\dots ,n\right\}$ can be uniquely determined by the cardinalities $|{S}_{i}\cap T|$ for $1\le i\le 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

• Questions are typically answered in as fast as 30 minutes

Solve your problem for the price of one coffee

• Math expert for every subject
• Pay only if we can solve it

ohhappyday890b
Step 1
Let T be the set of coins with weight 1. Then, the weight of the subset ${S}_{i}$ is precisely $|{S}_{i}\cap T|$.
Step 2
If we weigh each ${S}_{i}$, we will be able to recover T.
###### Did you like this example?
Ryder Ferguson
Step 1
Let the coins be ${C}_{1},\dots ,{C}_{n}$. Let T be the set of coins of weight 1, and let
$T=\left\{k\in \left\{1,\dots ,n\right\}:{C}_{k}\in \mathcal{T}\right\}\phantom{\rule{thickmathspace}{0ex}},$
the set of indices of those coins. For $k=1,\dots ,m$ let ${\mathcal{S}}_{k}=\left\{{C}_{k}:k\in {S}_{k}\right\}$, and let ${w}_{k}$ be the total weight of the coins in ${\mathcal{S}}_{k}$. Since each coin has weight 1 or 0, ${w}_{k}$ is the number of coins in ${\mathcal{S}}_{k}$ of weight 1, which is $|{\mathcal{S}}_{k}\cap \mathcal{T}|$. Thus,
${w}_{k}=|{\mathcal{S}}_{k}\cap \mathcal{T}|=|{S}_{k}\cap T|\phantom{\rule{thickmathspace}{0ex}}.$
Step 2
If you weigh each of the sets ${\mathcal{S}}_{k}$, those m weighings will give you the numbers $|{S}_{k}\cap T|$ for $k=1,\dots ,m$. If the sets ${S}_{k}$ are determining, those m numbers uniquely determine the set T, from which you immediately get $\mathcal{T}=\left\{{C}_{k}:k\in T\right\}$.