I often play the higher-lower game with my students. I randomly generate a number 1 to 1000 and give a student 10 guesses. After each guess I tell them whether the number is higher or lower. With good mental math skills a student should always win.
This is a new variant:
I pick two numbers from 1 to 1000 and create an ordered pair. The student guesses coordinates and I tell them both (east/west/neither) and (north/south/neither).
How many guesses should I give?
Yes, 10 questions will suffice. As Ady points out, the coordinates are independent.
But can it be done in less?
1 question can resolve 1 number
2 questions can resolve 3 numbers (2*1 + 1)
3 questions can resolve 7 numbers (2*3 + 1)
4 questions can resolve 15 numbers (2*7 + 1)
Oh, now I see. n questions can resolve 2^n - 1
5 questions can resolve 31 numbers (2*15 + 1)
6 questions can resolve 63 numbers (2*31 + 1)
7 questions can resolve 127 numbers (2*63 + 1)
8 questions can resolve 255 numbers (2*127 + 1)
9 questions can resolve 511 numbers (2*255 + 1)
So, 9 numbers are not guaranteed sufficient to both know the number and say it
10 questions can resolve 1023 numbers (2*511 + 1)
9 questions are enough to narrow it down to a single number, but more times than not the student needs the 10th "guess" to actually name the answer that is known to him after he has narrowed it down with the first 9 guesses.
Knowing and saying are not the same thing
