Application: Searching with lies, revisited

In the notation of Definition 3.6.1 above, we have the following solution to searching with one lie.

Lemma 3.8.6   If $M=2^{2^r-r-1}$, $r=2,3,...$, then $g(M,1)=2^r-1$.

Algorithmic ``proof'': A number from $1$ to $M$ has been choosen. One lie is allowed.

1. Write the number choosen in binary. Encode the number using a binary Hamming code $C$ with parameters
   length=$2^r-1$
   dimension = $2^r-r-1$
   minimum distance=3.
   (There is a ``good'' algorithm for this.) Recall that each Hamming $(n,k)$-code is $1$-error correcting.
2. Let $n=2^r-1$. Ask the $n$ Questions: ``Is the $i^{th}$ digit of the encoded number a $1$?'', $i=1,2,...,n$.
3. Let $w_i=1$ if the $i^{th}$ answer is ``yes'', let $w_i=0$ otherwise, and write ${\bf w}=(w_1,w_2,...,w_n)$.
4. Decode ${\bf w}$ to a Hamming codeword ${\bf c}$. (There is a ``good'' algorithm for this.)
5. Translate ${\bf c}$ into decimal.

This solves the searching with lies problem in the case where $M$ is the above power of $2$. The general problem has a similar solution, though the reasoning is a little more complicated. We refer to [Hi], [N]^3.2, and [Mont], for more details.