[Computational Complexity] Find the Number- again
- I was (once again) playing FIND THE NUMBER with a 10-year 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 even-ness 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 non-trivial 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