Earlier today I asked you the following puzzle.
Ask Johnny
Johnny thinks of a number between 1 and 1,000 inclusive. Your job is ask him questions to discover what that number is.
Johnny will always be truthful, to the best of his knowledge, but is only allowed to reply either “Yes”, “No” or “I don’t know.”
What is the fewest number of questions you need to ask Johnny in order to guarantee you will discover his number?
I explained how you can find the number after 10 questions. (You divide the available numbers into two equal sets, and ask Johnny whether it was in one of these sets. He replies “yes” or “no”, thus reducing the available numbers by half.)
I added that you can find the number in less than 10 questions. So, how did you get on?
Solution 7 questions.
The important observation in the question is to realise that Johnny can respond in one of three ways: “Yes”, “No” and “I don’t know.” You need to make use of all three possible responses to reduce the possible candidates to one third of the available numbers each time.
Here’s one way of doing this. Let your first question be: “I am thinking of a number between 333 and 666. Is your number smaller than mine?
If Johnny replies YES, you know his number is between 1 and 332.
If Johnny replies NO, you know his number is between 667 and 1,000.
If Johnny replies I DON’T KNOW, you know his number is between 333 and 666.
In other words, this question has reduced the amount of available numbers from 1000, to either 333 or 334. You have shrunk the target to a third of what it was. If you carry on shrinking the target to a third each time, you will hone in on Johnny’s number in seven questions. (If the interval left is the consecutive numbers between a and b, you can formulate each question as such: “I am thinking of a number between [a + (b-a)/3] and [a + 2(b-a)/3]. Is your number smaller than mine? )
What is particularly nice about this solution is that you are beating Johnny with his own weapon – not only does he “think of a number” but you do too.
I hope you enjoyed today’s puzzle. I’ll be back in two weeks.
I set a puzzle here every two weeks on a Monday. I’m always on the look-out for great puzzles. If you would like to suggest one, email me.
I’m the author of several books of puzzles, most recently the Language Lover’s Puzzle Book.
Today’s puzzle is adapted from The Bogotá Puzzles by Bernardo Recamán. Bernardo is a Colombian mathematician and the inventor of the Slightly Spooky Recamán Sequence.