Lesson 13

This can be done as follows. Let \(b_{3}b_{2}b_{1}b_{0}\) be the binary representation of \(x\): \[x=\sum_{i=0}^{3}b_{i}2^{i}=8b_{3}+4b_{2}+2b_{1}+b_{0}.\] Ask your friend to give you the values of \(b_{3},b_{2},b_{1},b_{0}\). Then, ask for the value of the checksum \[b_{3} \oplus b_{2} \oplus b_{1} \oplus b_{0} = (b_{3} + b_{2} + b_{1} + b_{0}) \bmod{2}.\] A simple, but crucial observation: the checksum is correct if and only if the five answers are correct. If the checksum is correct, then you have already guessed \(x\). In the remaining case, you know that one of the first five answers is wrong and that your friend cannot give you wrong answers anymore. Then, it is enough to find the index of the wrong answer, i.e., to guess a number \(1 \le q \le 5\). This can be done with three additional questions.