Question: 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. Ulam'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, 1/4 of the elements can be eliminated using two queries
c) Show from part (b) that if ƒ (n) equals the number of queries used to solve Ulam's problem using the method from part (b) and n is divisible by 4, then ƒ (n) = f (3n/4) + 2.
d) Solve the recurrence relation in part (c) for ƒ (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 Ulam's problem has been determined by A. Pelc [Pe87]