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.