Consider the following $(d,k,n)$-coin weighting (with spring scale):
You possess an electronic scale, $n$ coins, and $d$ of them are magnetic. Moreover, you always need to weight at least $k$ coins at the same time.
Let $S$ be a large set (say $S = \mathbb F_p$ for a large $p$), and $s\in S$ an unknown element. The scale has the following property: if a set of (at least $k$) normal coins are on it will consistently output $s$, and if a set containing at least one magnetic coin is weighted, the scale will output a random element of $S$.
Is it possible to find an algorithm that outputs two distinct sets (not necessarily disjoint) of coins having the same output in a minimal (expected) number of weightings $N$? Note that if $S$ is large enough, this is essentially the same as finding two sets that output $s$.
One can assume $d+t+1<n$ for the existence of a solution, but stronger conditions on $(d,n,t)$ can be imposed.
As a benchmark, if the sets are chosen completely at random, the expected value for $N$ is $$\mathbb{E}(N) = O\left(\exp\left(\frac{dk}{n}\right)\right).$$
Thanks!
