PUB - Publikationen an der Universität Bielefeld

We consider the problem of finding the minimal number L-l(M) of binary questions needed to find an unknown element of a set of cardinality M with a sequential strategy if at most I of the answers are lies. Obviously, in the case l = 0 [logM] questions are needed. Thus, one more question is necessary if the number of elements is doubled. We show that for every fixed 1 and sufficiently large M, then L-l(2M) less than or equal to L-l(M)+2 and moreover L-l((3)/M-2) less than or equal to L-l(M)+1. These bounds are sharp in infinitely many cases. As a consequence, at most one question more than the information theoretic lower bound is needed to successfully find the unknown number. One of our strategies uses the minimum amount of adaptiveness during the search process. (C) 2003 Elsevier B.V. All rights reserved.