Searching with lies, 2

In the previous post, we have seen how the number of questions needed to determine the number selected in the non-adaptive/”no feedback” situation is closely connected with the construction of “best possible” error-correcting codes. Let us look at some tables of specific values.

Odd M\leq 50:

\begin{array}{|c|c|c|}  M & f(M,1) & g(M,1) \\ \hline  11& 7& 7\\  13& 7& 7\\  15& 7& 7\\  17& 8& 9\\  19& 8& 9\\  21& 8& 9\\  23& 8& 9\\  25& 8& 9\\  27& 8& 9\\  29& 9& 9\\  31& 9& 9\\  33& 9& 9\\  35& 9& 10\\  37& 9& 10\\  39& 9& 10\\  41& 9& 10\\  43& 9& 10\\  45& 9& 10\\  47& 9& 10\\  49& 9& 10\\ \hline  \end{array}

Even M\leq 50:

\begin{array}{|c|c|c|}  M & f(M,1) & g(M,1) \\ \hline  10& 7& 7\\  12& 7& 7\\  14& 7& 7\\  16& 7& 7\\  18& 8& 9\\  20& 8& 9\\  22& 8& 9\\  24& 8& 9\\  26& 8& 9\\  28& 8& 9\\  30& 9& 9\\  32& 9& 9\\  34& 9& 10\\  36& 9& 10\\  38& 9& 10\\  40& 9& 10\\  42& 9& 10\\  44& 9& 10\\  46& 9& 10\\  48& 9& 10\\  50& 9& 10\\ \hline  \end{array}

Next, we tabulate some values of f(10^6, e) for different values of e\geq 0 (see R. Hill, J. Karim, E. Berlekamp, “The solution of a problem of Ulam on searching with lies,” IEEE, 1998):

\begin{array}{|c|c|}  e & f(M,e) \\ \hline  0 & 20 \\  1 & 25 \\  2 & 29 \\  3 & 33 \\  4 & 37 \\  5 & 40 \\  6 & 43 \\  7 & 46 \\  8 & 50 \\  9 & 53 \\  \vdots & \vdots \\  e & 3e+26 \\  \hline  \end{array}

What is remarkable, I think, is that even if you are allowed to modify your questions adaptively, depending on the answer given, it won’t help you very much.

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s