A room has n computers, less than half of which are damaged. It is possible to query a computer about the status of any computer. A damaged computer could give wrong answers. The goal is to discover an undamaged computer in as few queries as possible.
(Once again, posed by Gurmeet Singh Manku on his blog)
Highlight the part between the * symbols for the answer.
* [Thanks to Gaurav Bubna for his solution]
Pair up all the computers. In every pair, test one comp with other. We have 3 possibilities - correct correct, correct wrong, wrong wrong. correct correct can only come if both comps are either correct or both wrong. From each such pair just keep one comp.
Note that: Since for wrong wrong pairs and correct wrong pairs, both working can never be the case, so, in correct correct pairs, number of working > no of damaged.
So, the property number of working > no of damaged is preserved in the next iteration.
Note that we reduce number of elements bt more than half. So, T(n) < T(n/2) + n, i.e T(n) < 2n