Ulam's pathological liar game with one half-lie Academic Article uri icon


  • 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 ofnpossibilities withqyes-no questions, while the responder Carole is allowed to lie a fixed numberkof 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 withk+1lies 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 defineA1*(q)for the casek=1to be the minimum numbernsuch that Paul can prevent Carole from disqualifying allnelements inqrounds of questions, and prove thatA1*(q)~2q+1/q.

published proceedings

  • International Journal of Mathematics and Mathematical Sciences

author list (cited authors)

  • Ellis, R. B., & Yan, C. H.

citation count

  • 6

complete list of authors

  • Ellis, Robert B||Yan, Catherine H

publication date

  • December 2004