Lesson 5

It turns out that asking four nonadaptive questions is also possible. To do this you just ask your friend to reveal all four bits of the binary representation of \(x\).

A bit more formally, you may proceed as follows. Start by asking whether \(x\) belongs to the set \(S_{0}=\{1, 3, 5, 7, 9, 11, 13, 15\}\). This reveals the least significant bit of (the binary representation of) \(x\): it is equal to \([x \in S_{0}]\). Then, ask whether \(x\) lies in the set \(S_{1}=\{2, 3, 6, 7, 10, 11, 14, 15\}\). This gives you the next bit of \(x\). Continuing in the same manner, you get all four bits of \(x\).