Ulam's game, or the Rényi–Ulam game, is a mathematical game similar to the popular game of twenty questions where one attempts to guess an unnamed object with yes–no questions, but where some of the answers may be wrong. Alfréd Rényi (1961) introduced the game, though his paper was overlooked for many years. Rényi  reported the following story about the Jew Bar Kochba in 135 CE, who defended his fortress against the Romans. It is also said that Bar Kochba sent out a scout to the Roman camp who was captured and tortured, having his tongue cut out. He escaped from captivity and reported back to Bar Kochba, but being unable to talk, he could not tell in words what he had seen. Bar Kochba accordingly asked him questions which he could answer by nodding or shaking his head. Thus he acquired from his mute scout the information he needed to defend the fortress. Stanislaw Ulam (1976, p. 281) rediscovered the game, presenting the idea that there are a million objects and the answer to one question can be wrong. Pelc (2002) gave a survey of similar games and their relation to information theory.
- "How to Play Ulam's Game" (PDF). Retrieved 13 June 2013.
- Pelc, Andrzej (2002), "Searching games with errors---fifty years of coping with liars", Theoretical Computer Science, 270 (1): 71–109, doi:10.1016/S0304-3975(01)00303-6, ISSN 0304-3975, MR 1871067
- Rényi, Alfréd (1961), "On a problem in information theory", Magyar Tud. Akad. Mat. Kutató Int. Közl. (in Hungarian), 6: 505–516, MR 0143666
- Ulam, S. M. (1976), Adventures of a mathematician, Charles Scribner's sons, ISBN 978-0-520-07154-4, MR 0485098
|This mathematics-related article is a stub. You can help Wikipedia by expanding it.|