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?
For question 1, you need log_2 n questions. Ask if x is congruent to 0 mod 2. If it is, ask if it's congruent to 0 mod 4; if it's not, ask if it's congruent to 1 mod 4. Continue in this vein, basically building up the binary expansion of the number from the right, one bit at a time. On information-theoretic grounds you can't do better than getting one bit of information per question, so this is best possible.
ReplyDeleteFor question 2, I suspect the optimal strategy (at least as n goes to infinity) is to ask, each time, the question that rules out the largest portion of what remains of the search space. (This is basically a greedy algorithm.) This seems to mean that first you should pin down the number mod 2 (by asking one question), then mod 3 (two questions), then mod 5 (four questions), ...
Now for the asymptotics of that strategy. For any integer k, let k# be the product of all primes less than or equal to k. Then to distinguish any number between 1 and n, we need to ask ((2-1) + (3-1) + (5-1) + ... + (k-1)) questions, where k is the smallest prime such that k# is at least n. (For example, if n is between 7 and 30, then we'll determine the residue of the target number mod 2, mod 3, and mod 5 to determine the target number. Now, if n is between 7 and 15 then we only need to know two of those residues; I'm ignoring that, since I think that doing so will at worst mean that we look at one more prime than in the optimal strategy.)
Now, k# is roughly exp(k), so we'll end up taking k near log n. The sum of the primes up to x is of the order (x^2)/(2 log x), and I'll ignore the 1s getting subtracted off since I'm just trying to get leading-order asymptotics. Letting x = log n there, we find that
(log n)^2/(2 log log n)
questions are required. I suspect this is asymptotically the number of questions required, as n goes to infinity.
use the chinese remainder theorem for #2
ReplyDeleteI mean Apply Chinese remaindering recursively: Should give O(\prod log^i n) where log^i is the i^th iterated log. I think the Chinese remainder should also give the lower bound.
ReplyDeleteanonymous #2.
This problem (the general one) is well-known under the name of Ulam's game (or Ulam's problem).
ReplyDeleteTake a look for instance at http://www.usna.edu/Users/math/wdj/montague/montague_mathhonors1998-1999.html
Never mind open problems, I want this Alex as a grad student. Tell him we'll give him a big stipend.
ReplyDelete