Lesson 1

In this section, we will be solving the following problem.

Your friend has picked an integer \(0 \le x < 16\), and you would like to guess it by asking your friend as few binary questions as possible!

In the programming challenges below, to ask a binary question, you pick a subset \(S \subseteq \{0,1,\dotsc, 15\}\). Your friend then replies by \([x \in S]\) (this is the Iverson bracket: it is equal to \(1\) if \(x \in S\), and to \(0\) otherwise). Pass \(S\) as a \(\texttt{list}\). For example, to check whether \(x\) is a number from 1 to 10 that is divisible by three, pass \(\texttt{[3, 6, 9]}\). To check whether \(2 \le x < 6\), pass \(\texttt{list(range(2, 6))}\).