Solved: Suppose someone picks a number x from a set of n

Chapter 7, Problem 7.3.28

(choose chapter or problem)

Suppose someone picks a number x from a set of n numbers. A second person tries to guess the number by successively selecting subsets of the n numbers and asking the first person whether x is in each set. The first person answers either "yes" or "no." When the first person answers each query truthfully, we can find x using log n queries by successively splitting the sets used in each query in half. Ularn's problem, proposed by Stanislaw Ulam in 1976, asks for the number of queries required to find x, supposing that the first person is allowed to lie exactly once. a) Show that by asking each question twice, given a number x and a set with n elements, and asking one more question when we find the lie, Ulam's problem can be solved using 2 log n + 1 queries. b) Show that by dividing the initial set of n elements into four parts, each with n /4 elements, 114 of the elements can be eliminated using two queries. [Hint: Use two queries, where each of the queries asks whether the element is in the union of two of the subsets with n/4 elements and where one ofthe subsets of n /4 elements is used in both queries.] c) Show from part (b) that if fen) equals the number of queries used to solve Ularn's problem using the method from part (b) and n is divisible by 4, then fen) = f(3n/4) + 2. d) Solve the recurrence relation in part (c) for f(n). e) Is the naive way to solve Ulam's problem by asking each question twice or the divide-and-conquer method based on part (b) more efficient? The most efficient way to solve Ularn's problem has been determined by A. Pelc [Pe87].