zbMATH — the first resource for mathematics

Ulam’s searching game with lies. (English) Zbl 0674.90110
Summary: We determine the minimal number of yes-no queries sufficient to find an unknown integer between 1 and \(2^ m\) if at most two of the answers may be erroneous.

91A99 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] Czyzowicz, J; Mundici, D; Pelc, A, Solution of Ulam’s problem on binary search with two lies, J. combin. theory ser. A, 49, 384-388, (1988) · Zbl 0662.68059
[3] Pelc, A, Solution of Ulam’s problem on searching with a Lie, J. combin. theory ser. A, 44, 129-140, (1987) · Zbl 0621.68056
[4] 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
[5] Spencer, J, Guess a number—with lying, Math. mag., 57, No. 2, 105-108, (1984) · Zbl 0538.90110
[6] Ulam, S.M, Adventures of a Mathematician, (), 281 · 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.