You are in the room with n computers. Some of them are good, and some of them are bad. You can query any computer about the status of any computer in the room. Good computers will always tell you the truth. Bad computers can answer anything. You also know that there are more good computers in the room than bad ones. How will you find a good computer in the room, and how many queries will you need?
The idea is to construct a sequence of queries that produce the sequence of answers of the form “good -> good -> good … -> good”. We should be able to do so because we know that there are more good computers in the room than bad ones. After we queried all computers in the room and are left with this chain, we know that there is some good computer in the chain. Therefore, the last computer will be good. To be concrete, we can go as follows:
Pick any computer and query it about the status of some other computer. If it answers “good” – add it to the back of the chain; if it answers “bad” – discard both and don’t query them any more. Pick another computer and query it about the status of the last computer in the chain (if the chain is empty pick any computer that has not been discarded before). If it answers “good” – add it to the back of the chain; if it answers “bad” – discard it along with the last computer in the chain (so that chain shrinks by one in this case). Keep doing it. Your chain is guaranteed to be non-empty after all computers are queried because you always discard as many bad computers as good ones.
The number of queries required is n – 1.