Ulam's pathological liar game with one half-lie (Q1774771): Difference between revisions

Summary: We introduce a dual game to Ulam's liar game and consider the case of one half-lie. In the original Ulam's game, Paul attempts to isolate a distinguished element by disqualifying all but one of \(n\) possibilities with \(q\) yes-no questions, while the responder Carole is allowed to lie a fixed number \(k\) of times. In the dual game, Paul attempts to prevent disqualification of a distinguished element by `pathological' liar Carole for as long as possible, given that a possibility associated with \(k+1\) lies is disqualified. We consider the half-lie variant in which Carole may only lie when the true answer is `no'. We prove the equivalence of the dual game to the problem of covering the discrete hypercube with certain asymmetric sets. We define \(A^*_1(q)\) for the case \(k=1\) to be the minimum number \(n\) such that Paul can prevent Carole from disqualifying all \(n\) elements in \(q\) rounds of questions, and prove that \(A^*_1(q) \sim 2^{q+1}/q\).