16.5 Learning with unreliable query responses. Consider the problem where the learner must nd an integer x selected by the oracle within [n], where n  1 is given. To do so, the learner can ask questions of the form (x  m?) or

(x > m?) for m 2 [n]. The oracle responds to these questions but may give an incorrect response to k questions. How many questions should the learner ask to determine x? (Hint: observe that the learner can repeat each question 2k+1 times and use the majority vote.)