Determine the minimum number of coin-weighings 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 &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?


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?
I had a brief look at this paper, 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.