Home | People | Seminar | Working Group | Conferences | Resources

# Abstract

 Title:The HalfLie Problem 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 \emph{halflie}). We show that the maximal $A_k(q)$ for which Paul wins has the asymptotic form $A_k(q)=2^{q+k}k!q^{-k} + \Theta(2^qq^{-k-\frac{1}{2}}).$ Return to the seminar page. Home | People | Seminar | Working Group | Conferences | Resources Please send comments about this page to Maurice Rojas at rojas@math.tamu.edu. Last Modified on 25/Feb/02