How to find counterfeit coins on a precision scale if the weights of coins a priori unknown

Let us have a set of $n$ coins with the main part of them, namely at least $n-t$, are genuine. Genuine coins have the same weight, other coins can have different weights but no one of these weights are known. There is a precision scale that allows to know the exact weight of any subset of coins. What is the minimal number $Q(n,t)$ of non-adaptive weighings which allows to find weights for all coins?

We give the optimal solutions for $t=1$ and asymptotically optimal for $t-const$ with the number of weighings $Q(n,t)=t\log_2 n (1+o(1))$. It was previously known [1] that $Q(n,t)=O(t \ln n)$.

There are at least two open questions:

• to develop 'decoding' algorithm which finds weights for all coins with polynomial complexity;
  
• what is $Q(n,t)$ for $t=\lambda n$ and $n \to \infty$?

[1] Nader H. Bshouty, Hanna Mazzawi, On parity check (0, 1)-matrix over Zp, SODA '11: Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete algorithms, pp. 1383–1394, 2011.

Joint work with Elena Egorova