Solution of Ulam's problem on binary search with two lies (Q1114408)

Someone thinks of a number between one and one million (which is just less than \(2^{20})\). 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 less than \(\log_ 2(1,000,000)\). Now suppose one were allowed to lie once or twice, then how many questions would one need to get the right answer ? [\textit{S. M. Ulam}, ``Adventures of a mathematician'' (Scribner's (New York, 1976; Zbl 0352.01009), p. 281)]. We prove that Ulam's problem has the following solution: Theorem. Twenty-nine is the least number of yes-no questions sufficient to find an integer between one and one million, if up to two lies are allowed.