In the paper On two problems of information theory, 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?
