I was (once again) playing FIND THE NUMBER with a 10year old.
(For the first time see
here.)
BILL: I am thinking of a number between 1 and 1000
(I wasn't but I said I was in reality I would give the
answers that maximize how many questions.)
You can ask questions about it to try to see what it is.
ALEX: Is it &ge 500?
BILL: Yes (my thoughts: GOOD, Alex knows how to do this!)
ALEX: Is it &ge 750
BILL: Yes (my thoughts: GOOD, he should get it in 10 or so)
ALEX: Is it even?
BILL: Yes (yikes! How am I going to keep track of this? Why did
he go to evens?)
ALEX: Is it a square?
BILL: No (hmmm need to remember all the even square over 750).
Eventually he got it in 14 questions.
He then thought of a number
that I was trying to figure out. My first three
questions were of the type
is it bigger than.... He complained:
You're a math guy ask things that are more mathematical! You
know, primes, squares, cubes, things like that!
I asked about evenness and also (in our language) its congruence
class mod various numbers. I was tempted to ask
Does the number have any square factors? since this is pretty
good for cutting the search space nearly in half (for 1,...,1000)
but decided not to.
I did get it in about 12 questions, but note that he really did have a number
in mind and was not trying to maximize how many questions it would take me.
This leads to the following questions.
The first one is easy to get matching upper and lower bounds.
The second one I have an upper bound but no nontrivial lower bound.
In all cases the number is between 1 and n and you want to
minimize how many questions it takes to find the number.

If the game is restricted to questions of the form
is x &equiv a mod b then how many questions do you need?

If the game is restricted to questions of the form
is x &equiv a mod p where p is a prime then how many questions do you need?

Posted By GASARCH to
Computational Complexity at 8/03/2009 02:35:00 PM