Alfréd Rényi Institute of Mathematics, Hungarian Academy of Sciences (HAS), P.O.B. 127, H-1364 Budapest, Hungary
Abstract:
One unknown element of an n-element set is sought by asking if it is contained in given subsets. It is supposed that the question sets are of size at most k and all the questions are decided in advance, the choice of the next question cannot depend on previous answers. At most l of the answers can be incorrect. The minimum number of such questions is determined when the order of magnitude of k is n with <1. The problem can be formulated as determination of the maximum sized l-error-correcting code (of length n) in which the number of ones in a given position is at most k.