<p>I had a brief look at <a href="http://colt2009.cs.mcgill.ca/papers/004.pdf">this paper</a>, and it appears that the answer to your question is yes (that is - no need for randomization). Also, the Introduction section surveys previous algorithms, information theoretic lower bounds and so on.</p>

CC BY-SA 3.0
2013-06-23T14:01:55.623Z
This is Nader H. Bshouty, _Optimal algorithms for the coin weighing problem with a spring scale_, Conference on Learning Theory 2009.  http://colt2009.cs.mcgill.ca/papers/004.pdf
András Salamon
CC BY-SA 3.0
2012-02-10T16:14:22.427Z
2012-02-10T16:14:22.427Z
Shir
<p>In the paper <a href="http://www.renyi.hu/~p_erdos/1963-12.pdf">On two problems of information theory</a>,  Erdõs and Rényi give lower bounds on the minimum number of weighings one must do to determine the number of false coins in a set of $n$ coins.</p>

<p>More formally:</p>

<blockquote>
  <p>The false coins have a smaller weight than the right coins; the
  weights $a$ and $b &lt; a$ of both the right and false coins are known. A
  scale is given by means of which any number $\leq n$ of coins can be
  weighed together. Thus if we select an arbitrary subset of the coins
  and put them together on the scale, then the scale shows us the total
  weight of these coins, from which it is easy to compute the number of
  false coins among those weighed. The question is what is the minimal
  number, $A(n)$ of weighings by means of which the right and false coins
  can be separated?</p>
</blockquote>

<p>The trivial lower bound they initially provide is:</p>

<p>$n / \log_2 (n + 1)$. </p>

<p>This isn't hard to see why through various information-theoretic or combinatorial arguments. The problem is how to construct such sets to do these weighings? Are there algorithms that utilize a constructive proof to achieve these lower bounds without relying on randomness? Are there randomized algorithms that achieve these bounds?</p>

<ds.algorithms><reference-request><co.combinatorics><it.information-theory><randomized-algorithms>
Determine the minimum number of coin-weighings
Nicholas Mancuso
# Determine the minimum number of coin-weighings

(Asked by: username_0 on 2012-02-09)

In the paper [On two problems of information theory](http://www.renyi.hu/~p_erdos/1963-12.pdf), Erdõs and Rényi give lower bounds on the minimum number of weighings one must do to determine the number of false coins in a set of $n$ coins.

More formally:

> The false coins have a smaller weight than the right coins; the
> weights $a$ and $b < a$ of both the right and false coins are known. A
> scale is given by means of which any number $\leq n$ of coins can be
> weighed together. Thus if we select an arbitrary subset of the coins
> and put them together on the scale, then the scale shows us the total
> weight of these coins, from which it is easy to compute the number of
> false coins among those weighed. The question is what is the minimal
> number, $A(n)$ of weighings by means of which the right and false coins
> can be separated?

The trivial lower bound they initially provide is:

$n / \log\_2 (n + 1)$.

This isn't hard to see why through various information-theoretic or combinatorial arguments. The problem is how to construct such sets to do these weighings? Are there algorithms that utilize a constructive proof to achieve these lower bounds without relying on randomness? Are there randomized algorithms that achieve these bounds?

**Tags:** ds.algorithms, reference-request, co.combinatorics, it.information-theory, randomized-algorithms


---

## 1 answers

### Answer by username_1 on 2012-02-10. Score: 8 | Accepted answer

I had a brief look at [this paper](http://colt2009.cs.mcgill.ca/papers/004.pdf), and it appears that the answer to your question is yes (that is - no need for randomization). Also, the Introduction section surveys previous algorithms, information theoretic lower bounds and so on.

> **Comments:**
> **username_2**: This is Nader H. Bshouty, _Optimal algorithms for the coin weighing problem with a spring scale_, Conference on Learning Theory 2009.  http://colt2009.cs.mcgill.ca/papers/004.pdf  

---

