The halflie problem

Joel Spencer, Catherine H. Yan

Research output: Contribution to journalArticle

Abstract

In Ulam's game Paul tries to find one of n possibilities with q Yes-No questions, while responder Carole is allowed to lie a fixed number k of times. We consider an asymmetric variant in which Carole must say yes when that is the correct answer (whence the halflie). We show that the maximal Ak (q) for which Paul wins has the asymptotic form Ak(q) = 2q+k k!q-k + Θ(2q q-k-1/2).

Original languageEnglish (US)
Pages (from-to)69-89
Number of pages21
JournalJournal of Combinatorial Theory. Series A
Volume103
Issue number1
DOIs
StatePublished - Jul 2003

Keywords

  • Asymmetric packing
  • Asymptotic formula
  • Liar's game
  • Ulam's problem

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'The halflie problem'. Together they form a unique fingerprint.

  • Cite this