Twenty questions, in the degenerate case when 20 = lg(n)
August 3rd, 2009
A new post at Computational Complexity asks the following question:
(Problem 1.) You are trying to determine a secret integer x between 1 and n inclusive, using only queries of the form “is x = a (mod b)?” for integers a and b of your choosing. How many queries are required to determine x in the worst case?
And more restrictively,
(Problem 2.) Same as above but you are only allowed to make queries where b is prime.
The comments section seems to reveal at least a partial solution, but these are fun problems, so at least give them a shot before reading the solution there (or here.) If you’d like the solution spoiled anyway, read on! Read more…