20 Questions
18th September 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.
18th September 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.
September 20th, 2006 at 12:37 am
Is it an integer?
September 20th, 2006 at 6:33 am
Yes, it is an integer. [19 questions left]
September 21st, 2006 at 5:17 am
Is it positive?
September 21st, 2006 at 7:08 am
No, it is not positive. [18 questions left]
September 21st, 2006 at 9:28 am
Is the integer less than -100?
September 21st, 2006 at 10:24 am
No, the integer is not less than -100. [17 questions left]
September 21st, 2006 at 12:10 pm
And now, to get the exact range: Is the integer equal to 0 or -100?
September 21st, 2006 at 2:27 pm
No, the number is not equal to 0 or -100. [16 questions left]
September 21st, 2006 at 2:47 pm
All righty then. Is the integer even?
September 21st, 2006 at 3:44 pm
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
September 21st, 2006 at 5:37 pm
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.
September 21st, 2006 at 7:05 pm
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.?
September 21st, 2006 at 8:35 pm
15 questions left, I’m not too worried . . . yet.
Is the integer less than or equal to -50?
September 21st, 2006 at 9:16 pm
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.
September 22nd, 2006 at 2:46 am
Is the number between -50 and -23?
September 22nd, 2006 at 7:02 am
Yes, the number is between -50 and -23. [13 questions remaining]
September 22nd, 2006 at 7:06 am
Is the number between -45 and -25?
September 22nd, 2006 at 7:08 am
Yes, the number is between -45 and -25. [12 questions remaining]
September 22nd, 2006 at 8:15 am
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?
September 22nd, 2006 at 8:27 am
No, the number is not a multiple of 6. [11 questions remaining]
September 22nd, 2006 at 10:10 am
I’m sorry if I’m hogging all the questions.
Is the final digit in the integer greater than or equal to 6?
September 22nd, 2006 at 12:13 pm
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.
September 22nd, 2006 at 12:36 pm
There are only 3 possibilities left as far as I can see.
Is it -38?
September 22nd, 2006 at 12:56 pm
No, it is not -38. [9 questions remaining. Hopefully all 9 are not needed at this point!]
September 22nd, 2006 at 2:43 pm
Is it -28?
September 22nd, 2006 at 3:35 pm
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.
September 22nd, 2006 at 3:48 pm
Ah, yes. A perfect number: 1 + 2 + 4 + 7 + 14 = 28.