Home >
Seminars and Colloquia >
Abstracts

Applied Mathematics Seminar
Date/Time/Room:
Wednesday (11/10/2004) at 2:30pm in 304 Pickard Hall "The RenyiUlam liar Game with a HalfLiar"Abstract: The $q$round R\'enyiUlam liar game with $k$ lies on the set $[n]:=\{1,\ldots,n\}$ is a 2player perfect information zero sum game. In the game the questioner Paul tries to find one of $n$ possibilities with $q$ YesNo questions, while the 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{halfliar}). We prove the existence of a winning strategy for Paul to the existence of a packing of the discrete hypercube with certain relaxed Hamming balls, and 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}}). \]References: 1. N. Alon and J. Spencer, The Probabilistic Method, 2nd ed., John Wiley, 2000. 2. A. Pelc, Solution to Ulam's problem on searching with a lie, J. Combinatorial Theory, Ser. A. 44 (1987), 129142 3. A. R\'{e}nyi, {\em A Diary on Information Theory}, J. Wiley and Sons, 1984. 4. J. Spencer, Ulam's searching problem with a fixed number of lies, {\em Theoretical Computer Science} \textbf{95} (1992), 307321 5. S. M. Ulam, \textit{Adventures of a Mathematician}, Charles Scribners's Sons, New York, 1976.

