Ratewise-optimal non-sequential search strategies under constraints on the tests

Already in his Lectures on Search [A. Rényi, Lectures on the theory of search, University of North Carolina, Chapel Hill, Institute of Statistics, Mimeo Series No. 6007, 1969. [11]] Renyi suggested to consider a search problem, where an unknown x∈X={1,2,…,n}x∈X={1,2,…,n} is to be found by asking for containment in a minimal number m(n,k)m(n,k) of subsets A1,…,AmA1,…,Am with the restrictions |Ai|⩽k