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 andasking 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? The most efficient way to solve Ulam's problem has been determined by A. Pelc [Pe87].

In Exercises\(29 - 33\), assume that\(f\)is an increasing function satisfying the recurrence relation\(f(n) = af(n/b) + c{n^d}\), where \(a \ge 1,b\) is an integer greater than\(1\), and \(c\)and\(d\)are positive real numbers. These exercises supply a proof of Theorem\(2\).

Short answer

1. It is concludedthat Ulam's problem can be solve with at most \(2\log n + 1\) queries.
2. The required questions are "Is \(x\) within the set \(A \cup B\) ?" and "Is \(x\) within the set \(A \cup C\) ?"
3. The required expression is\(f(n) = f(3n/4) + 2\).
4. The required result is\(2m = \frac{{2\log n}}{{\log 4/3}}\).
5. The graph makes less queries in the naive way of part (a).

Step-by-step solution

Given expression

Given: number \(x\) and set with\(n\)elements.

Let us assume that \(n = {2^m}\)  for some nonnegative integer \(m\)

(a)

Base step:

If \(m = 1\) and\(n = 2\), then the set contains two elements\({a_1}\)and\({a_2}\).

Then we ask the question "Is\(x\)in this part of the set?" for the two sets\(\left\{ {{a_1}} \right\}\)and\(\left\{ {{a_2}} \right\}\).

If the answer is the same for the two questions, then both questions were answered truthfully and thus then we know in which set the element is. the test (does not matter which set). The answer to this question is then true and thus we then know in which subset the element is.

We then note that we make \(2 + 1 = 3\) queries in total.

\(\begin{array}{}f(2) = 2 + 1\\f(2) = 3\\f(2) = 2{\log _2}2 + 1\end{array}\)

and\(B\).

If the answer is the same for the two questions, then both questions were answered truthfully and thus then we know in which set the element is. the test (does not matter which set). The answer to this question is then true and thus we then know in which subset the element is. occur only once).

\(\begin{array}{}f(n) = 2m + 1\\f(n) = 2{\log _2}n + 1\end{array}\)

Thus, we then note that Ulam's problem can be solve with at most \(2\log n + 1\) queries.

Let us assume that\(n = {4^m}\)for some nonnegative integer\(m\)

(b)

Divide the set of \(n\) elements into 4 subsets $A, B, C, D$ of \({4^{m - 1}}\) elements each.

There are two questions:

"Is \(x\) within the set \(A \cup B\) ?"

"Is \(x\) within the set \(A \cup C\) ?"

If the answer to both questions is "Yes", then \(x\) is not within \(D\) and thus \(x\) is then within \(A \cup B \cup C\).

If the answer to both questions is "No", then \(x\) is not within \(A\) and thus \(x\) is then within \(B \cup C \cup D\).

If the answers are "Yes" then "No", then \(x\) is not within \(C\) and thus \(x\) is then within \(A \cup B \cup D\).

If the answers are "No" then "Yes", then \(x\) is not within \(B\) and thus \(x\) is then within \(A \cup C \cup D\).

Step 4:Let us assume that \(n = {4^m}\) for some nonnegative integer\(m\)

(c)

\(1/4\)of the elements were eliminated and thus \(3/4\) of the elements are remaining. In reducing the set, it also made two queries.

\(\begin{array}{l}f(n) = f(3/4(n)) + 2\\f(n) = f(3n/4) + 2\end{array}\)

Step 5:Repeatedly use the recursive relation

(d)

Let \(n = \frac{{{4^m}}}{{{3^m}}} = {\left( {\frac{4}{3}} \right)^m}\)

Repeatedly use the recursive relation in part (c):

\(\begin{array}{l}f(n) = f\left( {\frac{{3n}}{4}} \right) + 2\\f(n) = f\left( {\frac{{{3^2}}}{{{4^2}}}n} \right) + 2 + 2\end{array}\)

\(\begin{array}{l}f(n) = f(1) + 2 + \ldots + 2 + 2 + 2\\f(n) = 0 + 2 + \ldots + 2 + 2 + 2\end{array}\)$

The sum contains two \(m\) s.

\(\begin{array}{}2m = 2{\log _{4/3}}n\\2m = \frac{{2\log n}}{{\log 4/3}}\\2m \approx 4.8\log n\end{array}\)

Plot the graph

(e)

The naive way is better, because when \(n\) is large: \(1 + 2\log n < 4.8\log n\)

Thus, make less queries in the naive way of part (a).