zbMATH — the first resource for mathematics

Optimal comparison strategies in Ulam’s searching game with two errors. (English) Zbl 0902.90191
Summary: Suppose \(x\) is an \(n\)-bit integer. By a comparison question we mean a question of the form “does \(x\) satisfy either condition \(a< x< b\) or \(c< x< d\) ?”. We describe strategies to find \(x\) using the smallest possible number \(q(n)\) of comparison questions, and allowing up to two of the answers to be erroneous. As proved in this self-contained paper, with the exception of \(n=2\), \(q(n)\) is the smallest number \(q\) satisfying Berlekamp’s inequality \(2^{q}\geqslant 2^{n} ((^{q}_{2})+q+1)\). This result would disappear if we only allowed questions of the form “does \(x\) satisfy the condition \(a< x< b\) ?”. Since no strategy can find the unknown \(x\in \{0,1, \dots, 2^{n}-1\}\) with less than \(q(n)\) questions, our result provides extremely simple optimal searching strategies for Ulam’s game with two lies – the game of Twenty Questions where up to two of the answers may be erroneous.

91A46 Combinatorial games
Full Text: DOI
[1] Berlekamp, E.R., Block coding for the binary symmetric channel with feedback, (), 330-335 · Zbl 0176.49404
[2] Czyzowicz, J.; Mundici, D.; Pelc, A., Ulam’s searching game with lies, J. combinat. theory, 52, 62-76, (1989), Series A · Zbl 0674.90110
[3] Mac Williams, J.F.; Sloane, N.J.A., The theory of error-correcting codes, (1986), North-Holland Amsterdam
[4] Mundici, D., Logic of infinite quantum systems, Internat. J. theoret. phys., 32, 1941-1955, (1993) · Zbl 0799.03019
[5] Pelc, A., Solution of Ulam’s problem on searching with a Lie, J. combinat. theory series A, 44, 129-140, (1987) · Zbl 0621.68056
[6] Spencer, J., Ulam’s searching game with a fixed number of lies, Theoret. comput. sci., 95, 307-321, (1992) · Zbl 0749.90102
[7] 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.