2
$\begingroup$

I tried to solve the following problem, which I found in the book "Discrete Mathematics and Its Applications", by Kenneth Rosen (Problem 28 of the section 7.3 of the 6th Edition):

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. [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 of the subsets of $n/4$ elements is used in both queries.]

c) Show from part (b) that if $f (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 $f (n) = 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?

(Note: here, $\log n$ stands for the base-2 logarithm of $n$.)

I will post the whole solution as an answer to my own question, because I want to know if the solution is completely correct and consistent. Thank you in advance.

1 Answers 1