Nonadaptive search problem with sets of equal sum (Q1407191)

In this paper a nonadaptive seach problem for an unknown element \(x\) in the set \(A=\{1,\dots,2^n\}\), \(n \geq 3\), is considered. Given a natural number \(S\), we allow to ask whether \(x\) belongs to a subset \(B\) of \(A\) such that the sum of the elements of \(B\) equals \(S\). In this case \(B\) is called a question set of weight \(S\). Call a natural number \(S\) good if for some \(m\) there exists a collection \(B_1,B_2,\dots,B_m\) of question sets of weight \(S\) which determine \(x\). A good number \(S\) is called proper if \(m=n\). There are two problem of interest: Problem A. Find all good numbers \(S\). Problem B. Find all proper numbers \(S\). The complete answer of Problem A is given in the following Theorem. \(S\) is good if and only if \(S \in [2^n-1;2^{2n-1}-2^{n-1}+1]\). On the other hand, Problem B is solved as follows with some exception. Theorem. If \(S\) is proper then \[ S \in [2^{2n-2}+2^{n-2}-c; 2^{2n-2}+2^{n-2}+c], \quad\text{where}\quad c=\frac{1}{2}\binom{2n-1}{n-1}. \tag \(*\) \] Conversely if \(S\) satisfies \((\ast)\), then \(S\) is proper when \(n\) is not a power of 2. For the case \(n=2^k\), the sufficiency of \((\ast)\) is an open problem.