Lesson 15

There exists a set \(C \subseteq \{0,1\}^{7}\) with the following two properties: \(|C|=16\) and any two different strings \(u, v \in C\) differ in at least three positions. As \(C\) one can take, for example, the Hamming code: \[C=\{x \in \{0,1\}^{7} \colon Hx=\mathbf{0}\},\] where the matrix \(H \in \{0,1\}^{3 \times 7}\) contains as columns the binary representation of integers \(1,2,\dotsc,7\) and the multiplication is over \(\mathbb{F}_{2}\). \[H=\begin{pmatrix}0&0&0&1&1&1&1\\ 0&1&1&0&0&1&1\\ 1&0&1&0&1&0&1\end{pmatrix}\] We leave the proof of two properties of \(C\) mentioned above to you as an exercise. This is how one can generate the set \(C\) in Python.

from itertools import product

code = [x for x in product(range(2), repeat=7) if
        (x[3] + x[4] + x[5] + x[6]) % 2 == 0 and
        (x[1] + x[2] + x[5] + x[6]) % 2 == 0 and
        (x[0] + x[2] + x[4] + x[6]) % 2 == 0
        ]

for i, word in enumerate(code):
    print(i, end=' ')
    print(*word, sep='')

0 0000000
1 0001111
2 0010110
3 0011001
4 0100101
5 0101010
6 0110011
7 0111100
8 1000011
9 1001100
10 1010101
11 1011010
12 1100110
13 1101001
14 1110000
15 1111111

The set \(C\) allows you to proceed as follows. Give the list above to your friend and ask her to locate the \(x\)-th row in it and to send you the seven bits from this row. Even if your friend flips one of the seven bits, you will be able to recover the original sequence of seven bits (thanks to the property that every two sequences in \(C\) differ in at least three positions)!

Finally, this is how one can prove that at least seven questions are needed in any strategy. Assume that this can be done with six questions. Then, you not only learn \(x\), but also the index of the question where your friend gave you a wrong answer or the fact that there were no wrong answers. The total number of possibilities is \(16 \cdot 7=112\), but this is larger than \(2^{6}\).