 # Coin-weighting problem Let n coins of weights 0 and 1 be given. We are also given a scale with whic Callum Dudley 2022-07-01 Answered
Coin-weighting problem
Let n coins of weights 0 and 1 be given. We are also given a scale with which we may weigh any subset of the coins. The information from previous weighting may be used. The object is to determine the weights of the coins with the minimal number of weightings. Formally, a collection ${S}_{1},\dots ,{S}_{m}$ subsets of $\left\{1,\dots ,n\right\}$ is called 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.$. Let D(n) be the minimum m for which such a determing collection exists. Show that $D\left(n\right)\ge \frac{n}{{\mathrm{log}}_{2}\left(n+1\right)}$.
Let ${S}_{1},\dots ,{S}_{m}$ be an arbitrary determining collection. Also, assume that T be an arbitrary subset of $\left\{1,\dots ,n\right\}$. Then there are ${2}^{n}$ possibilities to choose T from $\left\{1,\dots ,n\right\}$. On the other hand, for each $1\le i\le m$, there are only $n+1$ possible $|{S}_{i}\cap T|$ because $0\le |{S}_{i}\cap T|\le |{S}_{i}|\le n$. But now I don't know how to apply the pigeonhole principle. This principle says that: if a set A consisting of at least $rs+1$ objects is partitioned into r classes, then some class receives at least $s+1$ objects. Equivalently, if $A=\bigcup _{i=1}^{r}{B}_{i}$ (disjoint union) and $|{B}_{i}|\le s$ for every $1\le i\le r$, then $|A|\le rs$. I can't use this principle in my answer. How can I introduce A and ${B}_{i}^{{}^{\prime }}s$ here? I was wondering if someone could help me about it.
You can still ask an expert for help

## Want to know more about Discrete math?

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

Solve your problem for the price of one coffee

• Math expert for every subject
• Pay only if we can solve it treccinair
Step 1
We see that a collection of m subsets ${S}_{1},{S}_{2},\dots ,{S}_{m}$ is determining if there exists a function f such that $f\left(|{S}_{1}\cap T|,|{S}_{2}\cap T|,\dots ,|{S}_{m}\cap T|\right)=T$ for every $T\subseteq \left\{1,2,\dots ,n\right\}$.
Step 2
The number of 'inputs' of f above is $\left(n+1{\right)}^{m}$, because $|{S}_{i}\cap T|$ has at most $n+1$ possible values (ranging from 0 to n). On the other hand, notice that there are ${2}^{n}$ possible subsets of $\left\{1,2,\dots ,n\right\}$. Hence, f must have at least ${2}^{n}$ possible 'inputs'. Therefore, $\left(n+1{\right)}^{m}\ge {2}^{n}$, which is equivalent to $m\ge \frac{n}{{\mathrm{log}}_{2}\left(n+1\right)}$.

We have step-by-step solutions for your answer!