James Bond is invited to a party with altogether $128$ participants (including Bond himself, the host, and the hostess). At the beginning of the party the host takes James Bond aside and asks him to identify the mysterious Doctor No. It is known that Doctor No knows all the other people at the party, but none of the others does know Doctor No.
James Bond starts asking questions of the following type: he asks some person A, whether A knows some other person B.
What is the minimal number of questions which James Bond needs to ask (in the worst case) to identify the mysterious Doctor No?
Answer
When James Bond asks A if he knows B:
If the answer is yes, this eliminates B as a candidate, since no one is supposed to know Doctor No.
If the answer is no, this eliminates A as a candidate, since Doctor No is supposed to know everyone.
James Bond just keeps asking an arbitrary non-eliminated person about another arbitrary non-eliminated person. Every question eliminates one person. At the beginning there are 125 candidates: 128 participants minus James Bond (whom the host knows), minus the host (whom James Bond knows), minus the hostess (whom the host knows).
So the answer is...
...124 questions in the worst case.
No comments:
Post a Comment