Ulam's game

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 [69] 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.