Lesson 6

Recall that to prove that the minimum number of questions needed to guess an integer \(0 \le x < 16\) is equal to four, one needs

1. to come up with a strategy with four questions, and
2. to prove that any strategy with at most three questions works incorrectly for some \(0 \le x < 16\).

Theorem. The minimum number of questions needed to guess an integer \(0 \le x < n\) is \(\lceil \log_{2} n \rceil\).

Proof. To prove an upper bound on the minimum number of questions, it is enough to present a protocol: in \(\lceil \log_{2} n \rceil\) questions, one can reveal all bits of (the binary representation of) \(x\).

Below, we give two different proofs of a lower bound.

• Protocol transcript. Given \(k\) answer bits, you (or your function \(\texttt{guess\_{number}(answers)}\)) need to be able to recover \(x\). There are at most \(2^{k}\) possibilities for \(k\) bits. Hence, if \(2^{k} < n\), then the protocol is incorrect for sure.


• Adversary argument. Instead of fixing an integer \(0 \le x < n\), your friend may proceed as follows. Each time she receives a question of the form “Is \(x\) in \(S\)?” from you, she answers in a way that leaves as many candidate solutions as possible. This way, she guarantees that, with every question, you at most halve the number of candidate solutions. In turn, this means that if you ask less than \(\lceil \log_{2} n \rceil\) questions, then the number of candidates is still greater than one.