In one variant of the classic counterfeit coins problem you are given a bag of $n$ numbered but otherwise identical looking coins and a scale and your job is to find which coins are counterfeit. Counterfeit coins all have one weight and the other coins all have another weight. The scale can only tell you if two sets of coins have the same weight, or which one of the two is heavier.
I am interested in a small extension where rather than using scales you can explicitly weigh sets of coins (on a digital scale, say). For simplicity let us also set the weights of the coins to either $1$ or $0$ depending on whether they are counterfeit or not. How many weighings do you need to be sure to determine which of the coins are counterfeit? I am interested in large $n$ answers. Bounds or asymptotic results (or references to them) would be really great.
The first observation is that if $n>4$ you can always get away with fewer than $n$ weighings.
I have the book "Combinatorial group testing and its applications" by Hwang and Du but I can't find any reference to this version of the problem. (See http://bit.ly/1cACC2G for Google books link.)
[Equivalent problem posted to https://math.stackexchange.com/questions/600328/a-whats-my-vector-game before I had reformulated it as this classic looking counterfeit coin problem. I have also posted some explicit solutions for small $n$ there.]
Best Answer
This problem was solved (up to a small multiplicative factor) by Erdos and Renyi: http://www.renyi.hu/~p_erdos/1963-12.pdf
Ps. Wow, Douglas Zare has a good intuition!