Ulam's game

In mathematics, Ulam's game, or the Rényi–Ulam game, is the problem of trying to guess an object with yes-no questions, where some of the answers may be wrong. Rényi (1961) introduced the game, though his paper was overlooked for many years, and Ulam (1975, p. 281) rediscovered the game, asking about the case where 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.

References

• 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, MR1871067 
• Rényi, Alfréd (1961), "On a problem in information theory" (in Hungarian), Magyar Tud. Akad. Mat. Kutató Int. Közl. 6: 505–516, MR0143666 
• Ulam, S. M. (1976), Adventures of a mathematician, Charles Scribner's sons, ISBN 978-0-520-07154-4, MR0485098, http://books.google.com/books?id=U2_zEZOHdU4C