Searching with a lie using only comparison questions
Duncan Innes · 2003
S.M. Ulam (Adventures of Mathematician Scribner, New York, 1976) presented the following problem. If one person picks a number from one to one million and the other person could ask yes or no questions, how many questions would be required to find the number with certainty if the opponent were allowed to lie once or twice. J. Spencer (Mathematics Magazine vol.57, no.2, 1984) found that by using a weight balancing strategy, if nc' are allowed. However, it will be shown that, by using a somewhat modified algorithm, if n>