Solution of Ulam's problem on searching with a lie (Q1090471)

From MaRDI portal
Revision as of 18:17, 12 July 2023 by Importer (talk | contribs) (‎Created a new Item)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
scientific article
Language Label Description Also known as
English
Solution of Ulam's problem on searching with a lie
scientific article

    Statements

    Solution of Ulam's problem on searching with a lie (English)
    0 references
    0 references
    1987
    0 references
    \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.
    0 references
    searching
    0 references
    minimal number of yes-no queries
    0 references

    Identifiers