20 Questions
Posted by Mr. B on September 18, 2006
I’m thinking of a real number. What is it?
You’ve got 20 yes/no questions at your disposal.
Whenever you are ready, ask.
Naught Much.com
Musings and Experiences of a High School Mathematics Teacher
Syndicate
Dan said
Is it an integer?
Mr. B said
Yes, it is an integer. [19 questions left]
Elias said
Is it positive?
Mr. B said
No, it is not positive. [18 questions left]
Mr. Person said
Is the integer less than -100?
Mr. B said
No, the integer is not less than -100. [17 questions left]
Mr. Person said
And now, to get the exact range: Is the integer equal to 0 or -100?
Mr. B said
No, the number is not equal to 0 or -100. [16 questions left]
Mr. Person said
All righty then. Is the integer even?
jd2718 said
I don’t want to interrupt the chain of questioning, but there is something to say about how best to attack a list (once it is down to a finite number) You’ll reach the answer without my help, but dividing into fibonacci numbers is (I seem to recall) optimal
Mr. B said
Yes, the number is even. [15 questions remaining]
It looks like you’re honing in quickly on the number.
Jd2718, could you be more specific with what you mean by “dividing into fibonacci numbers”? It sounds interesting.
jd2718 said
if we had 1 – 144 and we could ask about a group of numbers, one might assume that the optimal strategy would be to ask about half of the remaining numbers each time:
72/72, 36/36, 18/18, 9/9, 5/4, 3/2, 2/1 (worst case each time)
My recollection is that dividing ‘fibonacci’ is more efficient:
55/89, 55/34, 21/34, 21/13, 13/8, 8/5 looks worse, but that’s with bad luck on each guess. The math needs another look, but on average I think that we get there quicker this way.
Or maybe I am remembering wrong.?
Mr. Person said
15 questions left, I’m not too worried . . . yet.
Is the integer less than or equal to -50?
Mr. B said
No, the integer is not less than or equal to -50. [14 questions remaining]
Here’s a hint if you want to make an early guess: The product of -1 and the number you’re searching for has significance in the field of number theory.
Dan said
Is the number between -50 and -23?
Mr. B said
Yes, the number is between -50 and -23. [13 questions remaining]
jd2718 said
Is the number between -45 and -25?
Mr. B said
Yes, the number is between -45 and -25. [12 questions remaining]
Mr. Person said
The number 40 has significance because of n^2 − n + 41, but I’ll just wonder that to myself for the moment.
Is the integer a multiple of 6?
Mr. B said
No, the number is not a multiple of 6. [11 questions remaining]
Mr. Person said
I’m sorry if I’m hogging all the questions.
Is the final digit in the integer greater than or equal to 6?
Mr. B said
Yes, the final digit in the integer is greater than or equal to 6. [10 questions remaining]
Don’t sweat it about being a question hog.
Mr. Person said
There are only 3 possibilities left as far as I can see.
Is it -38?
Mr. B said
No, it is not -38. [9 questions remaining. Hopefully all 9 are not needed at this point!]
Mr. Person said
Is it -28?
Mr. B said
YES, the number is -28! It was found on the twelfth question. Not bad.
Now, what is special about the number 28? Hint: 6 is special in the same way.
Mr. Person said
Ah, yes. A perfect number: 1 + 2 + 4 + 7 + 14 = 28.