Solution of Ulam's problem on searching with a lie (Q1090471): Difference between revisions

\textit{S. M. Ulam} [''Adventures of a mathematician'' (1976; Zbl 0352.01009)] stated the following problem: what is the minimal number of yes-no queries needed to find an integer between one and one million, if one lie is allowed among the answers. \textit{R. L. Rivest}, \textit{A. R. Meyer}, \textit{D. J. Kleitman}, \textit{K. Winkelmann} and \textit{J. Spencer} [J. Comput. Syst. Sci. 20, 396-404 (1980; Zbl 0443.68043)] and \textit{J. Spencer} [Math. Mag. 57, 105-108 (1984; Zbl 0538.90110)] gave partial solutions by establishing bounds for the minimal number of queries necessary to find a number in the set \(\{\) 1,...,n\(\}\). Applied to the original question both solutions yield two possibilities: 25 or 26. We give an exact solution of Ulam's problem in the general case. For \(n=10^ 6\) the answer turns out to be 25. We also give an algorithm to perform the search using the minimal number of queries.