View source for Ulam's game

{{Short description|Mathematical guessing game}}
'''Ulam's game''', or the '''Rényi–Ulam game''', is a mathematical game similar to the popular game of twenty questions. In Ulam's game, a player attempts to guess an unnamed object or number by asking yes–no questions of another, but ''one'' of the answers given may be a lie.<ref>{{cite web|title=How to Play Ulam's Game|url=http://math.iit.edu/~rellis/papers/9how.pdf|access-date=13 June 2013}}</ref>

{{harvs|txt|first=Alfréd|last=Rényi|year=1961}} introduced the game in a 1961 paper, based on Hungary's Bar Kokhba game, but the paper was overlooked for many years.

{{harvs|txt|first=Stanisław|last=Ulam|year=1976|loc=p. 281}} rediscovered the game, presenting the idea that there are a million objects and the answer to one question can be wrong, and considered the minimum number of questions required, and the strategy that should be adopted.<ref>{{cite arXiv |eprint=1609.07367|last1=Beluhov|first1=Nikolai|title=Renyi-Ulam Games and Forbidden Substrings|year=2016|class=math.CO}}</ref> {{harvtxt|Pelc|2002}} gave a survey of similar games and their relation to [[Information theory|information theory]].

==See also==
* Knights and Knaves

==References==
<references />

*{{Citation | last1=Pelc | first1=Andrzej | title=Searching games with errors—fifty years of coping with liars | doi=10.1016/S0304-3975(01)00303-6 | mr=1871067 | year=2002 | journal=Theoretical Computer Science | issn=0304-3975 | volume=270 | issue=1 | pages=71–109| doi-access=free }}
*{{Citation | last1=Rényi | first1=Alfréd | title=On a problem in information theory | language=hu | mr=0143666 | year=1961 | journal=Magyar Tud. Akad. Mat. Kutató Int. Közl. | volume=6 | pages=505–516}}
*{{Citation | last1=Ulam | first1=S. M. | title=Adventures of a mathematician | url=https://books.google.com/books?id=U2_zEZOHdU4C | publisher=Charles Scribner's sons | isbn=978-0-520-07154-4 | mr=0485098 | year=1976}}

[[Category:Information theory]]



{{Sourceattribution|Ulam's game}}