Аннотация:
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.
