Let f(t)(n) be the number of questions necessary to find an unknown el
ement out of a set of n elements with a q-ary search process when up t
o t answers may be wrong (are lies). For q = 2, this problem was treat
ed by several authors. We give the complete solution for t = 1 and der
ive bounds for general t. Further, it is shown that the corresponding
function g(1)(n) for the non-adaptive case (which requires constructio
n of 1-error correcting codes) differs from f(1)(n) by at most 1, when
q is a prime power. (C) 1996 Academic Press, Inc.