Question 26
Leonardo thought of an integer between $1$ and $2003$ inclusive, and Julian has to guess that number. To do this, you can ask Leonardo questions that can be answered with yes or no. Leonardo is obliged to answer all the questions, but, if he wishes, he can lie at most once. (Some possible questions are, for example, "Is your number greater than $50$ and less than $1007$?" or "Was the answer you gave to my third question true?") Show that Julian can determine Leonardo's number with certainty using $15$ questions or fewer.