Searching with lies
R. Hill · Cambridge University Press eBooks · 1995
INTRODUCTION Consider a game of Twenty Questions in which someone thinks of a number between one and one million. A second person is allowed to ask questions to each of which the first person is supposed to answer only yes or no. Since one million is just less than 2 20 , it is clear that a “halving” strategy (i.e. asking “Is the number in the first half million?”, and so on) will determine the number within twenty questions. But now suppose that up to some given number e of the answers may be lies. How many questions does one now need to get the right answer? This is Ulam's searching problem, posed by Stanislaw Ulam (1976) in his autobiography “The Adventures of a Mathematician”. The problem has recently been solved for all values of e (for the cases of both 2 20 and 10 6 objects). We give the solution in Figure 1 and an outline of the proof in Section 3. More generally, we may consider the problem of finding the smallest number f(M,e) of yes-no questions sufficient to determine one of M objects if up to e of the answers may be lies. In Section 4, we survey the present state of knowledge regarding this function. In Section 5, we consider a version of Ulam's problem without feedback, where all the questions must be asked in advance of receiving any answers. This is equivalent to a problem in the theory of error-correcting codes.