|
|||||
|
|
How to play the one-lie Rényi-Ulam game |
|
| Authors: | Robert B. Ellis Catherine H. Yan |
| Affiliation: | a Department of Applied Mathematics, Illinois Institute of Technology, Chicago, IL 60616, United States b Department of Mathematics and Statistics, San Diego State University, San Diego, CA 92182, United States c Department of Mathematics, Texas A&M University, College Station, TX 77843, United States d Center for Combinatorics, LPMC, Nankai University, Tianjin 300071, PR China |
| Abstract: | The one-lie Rényi-Ulam liar game is a two-player perfect information zero-sum game, lasting q rounds, on the set [n]?{1,…,n}. In each round Paul chooses a subset A⊆[n] and Carole either assigns one lie to each element of A or to each element of [n]?A. Paul wins the original (resp. pathological) game if after q rounds there is at most one (resp. at least one) element with one or fewer lies. We exhibit a simple, unified, optimal strategy for Paul to follow in both games, and use this to determine which player can win for all q,n and for both games. |
| Keywords: | Ré nyi-Ulam game Pathological liar game Searching with lies |
| 本文献已被 ScienceDirect 等数据库收录！ | |