The case of one lie

The theory of Hamming codes allows us to solve the searching with lies (without feedback) problem when only one lie is told. In the notation of Definition 3.12.1 above, we have the following solution to searching with one lie.

Lemma 3.12.3   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.