Ulam's searching game with a fixed number of lies (Q1184984): Difference between revisions

From MaRDI portal
RedirectionBot (talk | contribs)
Changed an Item
ReferenceBot (talk | contribs)
Changed an Item
 
(One intermediate revision by one other user not shown)
Property / MaRDI profile type
 
Property / MaRDI profile type: MaRDI publication profile / rank
 
Normal rank
Property / cites work
 
Property / cites work: Ulam's searching game with lies / rank
 
Normal rank
Property / cites work
 
Property / cites work: Ulam's searching game with two lies / rank
 
Normal rank
Property / cites work
 
Property / cites work: Coping with errors in binary search procedures / rank
 
Normal rank
Property / cites work
 
Property / cites work: Solution of Ulam's problem on searching with a lie / rank
 
Normal rank
Property / cites work
 
Property / cites work: Balancing games / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4121861 / rank
 
Normal rank

Latest revision as of 15:16, 15 May 2024

scientific article
Language Label Description Also known as
English
Ulam's searching game with a fixed number of lies
scientific article

    Statements

    Ulam's searching game with a fixed number of lies (English)
    0 references
    28 June 1992
    0 references
    There 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 \textit{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.
    0 references
    Ulam's game with lies
    0 references
    0 references

    Identifiers