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


  [1]: http://www.renyi.hu/~p_erdos/1963-12.pdf