zbMATH — the first resource for mathematics

Solution of Ulam’s problem on searching with a lie. (English) Zbl 0621.68056
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. R. L. Rivest, A. R. Meyer, D. J. Kleitman, K. Winkelmann and J. Spencer [J. Comput. Syst. Sci. 20, 396-404 (1980; Zbl 0443.68043)] and 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.

68T99 Artificial intelligence
68P10 Searching and sorting
91A80 Applications of game theory
Full Text: DOI
[1] Berlekamp, E.R, Block coding for the binary symmetric channel with noiseless, delayless feedback, (), 61-85 · Zbl 0176.49404
[2] Ravikumar, B; Lakshmanan, K.B, Coping with known patterns of lies in a search game, Theoret. comp. sci., 33, 85-94, (1984) · Zbl 0544.90105
[3] Rivest, R.L; Meyer, A.R; Kleitman, D.J; Winklmann, K; Spencer, J, Coping with errors in binary search procedures, J. comput. system sci., 20, 396-404, (1980) · Zbl 0443.68043
[4] Spencer, J, Guess a number—with lying, Math. mag., 57, No. 2, 105-108, (1984) · Zbl 0538.90110
[5] Ulam, S.M, Adventures of a Mathematician, (1976), Scribner’s New York · Zbl 0352.01009
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.