[Algorithms] Finding numbers
Posted on 2004-09-03
Suppose x, y (distinct) belongs to a set of integers from 0 to n-1.
Consider a game bwetween players A and B. PLayer A keeps the 2 numbers x, y. B wants to find out x, y by asking questions.
a) Suppose A will reply either Yes or No. At least how many quetions B must ask to determine x, y?
My ans which i think is not correct: log (n) + log (n-1)
b) Suppose B can ask A in the following way:
B gives A a number r.
A tells B whether x > r, and whether y > r.
Hence for one question asked by B, there are 4 possible outcomes from A.
What's a good algorithm for B?