A New Twist in a Famous Problem

26th December 2025, 05:27 pm

I recently gave my STEP students a question from our old 2014 PRIMES entrance test.

Puzzle. John’s secret number is between 1 and 216 inclusive, and you can ask him yes-or-no questions, but he may lie in response to one of the questions. Explain how to determine his number in 21 questions.

Here is the standard solution. We start by asking John to convert his number into binary and add zeros at the beginning if needed to make the result a binary string of length 16. For the first 15 questions, we do the following. For question i, we ask: “Is the i-th digit of your string zero?” For question 16, we ask, “Have you lied in response to a previous question?” If he lied on a previous question, he must say YES. If he didn’t, he might lie on question 16 and also say YES. In any case, if the answer is NO, he didn’t lie on the first 15 questions and we know the first 15 digits of the number. Then, we ask about the last digit three times, and the answer given at least twice is correct, so we know the number.

If the answer to question 16 is YES, then he lied on one of the questions 1–16. From now on, he has to tell the truth since he already lied. We use binary search (4 questions) to determine on which question he lied. This will tell us the first 15 digits, and we can use the 21st question to find the last digit.

One of my students, Tanish, invented an out-of-the-box solution that uses 18 questions. The idea is to force John to lie in the first two questions, and then safely proceed with the binary search.

He suggested asking the following two questions: “Are you going to answer NO in response to the next question?” and “Did you respond YES to the previous question?” The reader can check that whatever John replies, he is forced to lie exactly once.

Another student, Vivek, had a similar idea but used only one question to force John to lie: “Will you say NO to this question?”

Share: