Solved

# [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)

Any suggestions?

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?

???