|
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. Please send comments about this page to Maurice Rojas at rojas@math.tamu.edu. Last Modified on 25/Feb/02 |