J. Czyzowicz, D. Mundici, A. Pelc, Solution of Ulam's problem on binary search with two lies, Journal of Combinatorial Theory, Series A, 49 (1988), pp. 384-388.
Someone thinks of a number between one and one million (which is just less than 220). Another person is allowed to ask up to twenty questions, to each of which the first person is supposed to answer only yes or no. Obviously the number can be guessed by asking first: Is the number in the first half million? then again reduce the reservoir of numbers in the next question by one-half, and so on. Finally the number is obtained in at most the ceiling of log2(1,000,000) (i.e., 20) questions. Now suppose one were allowed to lie once or twice, then how many questions would one need to get the right answer?-S.M. Ulam, `` Adventures of a Mathematician '', p. 281, Scribner's, New York, 1976. We prove that the least number of questions always sufficient to get the right answer assuming at most 2 lies, is 29.
A. Pelc, Prefix search with a lie, Journal of Combinatorial Theory, Series A, 48 (1988), pp. 165-173.
We investigate the problem of finding an unknown leaf in a full binary tree, allowing the questioner to ask only queries whether the hidden leaf is in a given full subtree and assuming that one of the opponent's answers may be erroneous. We give the worst-case minimal number of queries sufficient to perform this search and provide an optimal algorithm.