Finding counterfeit coins Suppose I have $N$ rare coins, of which $M \le N$ are counterfeits. I am blind. I ask an oracle who charges me a penny to tell me in yes/no answers whether there is a counterfeit in any group I show her. Is there a strategy to identify all $M$ coins with minimal cost, preferably something better than $O(N)$?
This sounds like a variant of the counterfeit coin problem but I cannot find a good solution.
EDIT: In the case of $M=1$, one obvious solution is on order of $\log_2(N)$ where you number each coin in order, in base $2$. Then test each group by digits wherever the coin has a 1 in that digit. Then the counterfeit should be identified by the oracle readout per digit, in base $2$.
 A: For $M=2$ you can do it in $2 \log_2 N$ by the same binary search as for $M=1$.  Split the coins into two halves and ask about one half.  If you get yes, ask about the other.  If you get yes again, you have two binary searches for one coin each.  If you get no, you are looking for two coins in $\frac N2$.  You save one question if you get a no the first time while you have not separated the pair because you don't have to ask about the second half.
The information theoretic approach would be to try to keep the probability of each answer close to $\frac 12$.  If you ask about a group of $k$ coins, the chance of a no answer is $\left( 1-\frac MN\right)^k$.
$$\left( 1-\frac MN\right)^k=\frac 12\\
k \log \left( 1-\frac MN\right)=-\log 2\\
k=-\frac {\log 2}{\log \left(1-\frac MN\right)}$$
This does not account for the effects of the coins being discrete, but if you have $10\%$ counterfeits you should ask about groups of $6$ or $7$
My proposed strategy for large $N$ and at least moderate $M$, which I have not proven optimal, would be to compute $k$ from the above and ask about a group of $k$ coins.  If you get no, discard the coins, update $N$ and continue.  If you get yes, solve the $k$ coins and update both $M,N$ for the next group.  Since the group will be small and you are not certain how many counterfeits are in it, it is probably optimal to just ask coin by coin.  There is an opportunity to optimize the endgame where $N$ is not large.
