A simple solution to Ulam's liar game with one lie (Q952012): Difference between revisions

In the general form of Ulam's liar game between a questioner and a responder, the responder thinks of an integer \(x\) in \(\{1, \ldots,n\}\) and the questioner must determine \(x\) by asking questions the answers to which are ``yes'' or ``no''. The responder is allowed to lie on at most \(k\) of the responses. Let \(q_k(n)\) denote the maximum number of questions needed by the questioner, in an optimal strategy, to determine \(x\). Based on earlier work by \textit{R. L. Rivest} et al. [J. Comput. Syst. Sci. 20, 396--404 (1980; Zbl 0443.68043)], \textit{A. Pelc} [J. Comb. Theory, Ser. A 44, 129--140 (1987; Zbl 0621.68056)] determined \(q_1(n)\) for all \(n\). The authors of the present paper give a relatively simple strategy and analysis for the game with \(k=1\) which implies the result of Pelc for many values of \(n\).