Ulam’s searching game with a fixed number of lies.

*(English)*Zbl 0749.90102There are three integer parameters, \(n\), \(q\), and \(k\), in the (2-player) game of the title. Carole thinks of an integer \(x\) from \(1,2,\dots,n\). Paul may ask \(q\) questions, of the form “is \(x\) in \(A\)?”, where \(A\) is a subset of \(1,2,\dots,n\), and may use previous answers to decide his next question. Carole may lie at most \(k\) times in answering the questions. Paul wins if after \(q\) questions \(x\) is uniquely determined. If \(k=0\) it is obvious that Paul has a sure win if and only if \(n=2^ q\). The case \(k=1\) was solved by A. Pelc [J. Comb. Theory, Ser. A 44, 129-140 (1987; Zbl 0621.68056)] and several other recent papers have obtained partial results for \(k>1\). In the present paper a generalization of the game with \(n\) replaced by a sequence of nonnegative integers \(x_ 0,x_ 1,\dots,x_ k\) is analyzed. Let \(A_ 0,A_ 1,\dots,A_ k\) be disjoint sets with \(| A_ i|=x_ i\). Carole selects \(x\in A_ 0\cap\cdots\cap A_ k\). If \(x\in A_ i\) then Carole is permitted to lie at most \(k-i\) times. The original game is the case \(x_ 0=n\), \(x_ 1=\cdots=x_ k=0\). For fixed \(k\), and \(q\) sufficiently large and dependent on \(k\), necessary and sufficient conditions on \(n\) for Paul to have a sure win in the generalized game are obtained.

Reviewer: G.A.Heuer (Moorhead)

##### Keywords:

Ulam’s game with lies
PDF
BibTeX
XML
Cite

\textit{J. Spencer}, Theor. Comput. Sci. 95, No. 2, 307--321 (1992; Zbl 0749.90102)

Full Text:
DOI

##### References:

[1] | Czyzowicz, J.; Mundici, D.; Pelc, A., Ulam’s searching game with lies, J. combin. theory ser. A, 52, 62-76, (1989) · Zbl 0674.90110 |

[2] | Guzicki, W., Ulam’s searching game with two lies, J. combin. theory ser. A, 54, 1-19, (1990) · Zbl 0712.68027 |

[3] | Kleitman, D.J.; Meyer, A.R.; Rivest, R.L.; Spencer, J.; Winklmann, K., Coping with errors in binary search procedures, J. comput. system sci., 20, 396-404, (1980) · Zbl 0443.68043 |

[4] | Pelc, A., Solution of Ulam’s problem on searching with a Lie, J. combin. theory ser. A, 44, 129-140, (1987) · Zbl 0621.68056 |

[5] | Spencer, J., Balancing games, J. combin. theory ser. B, 23, 68-74, (1977) · Zbl 0374.90088 |

[6] | Ulam, S., Adventures of a Mathematician, (1977), Scribners 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.