Problem 44708. Sherlock Holmes: The Spy Problem

A guest at a party is a spy if this person is not known by any other guest, but knows all of them. There is at most one spy at a party, for if there were two spies, they would not know each other. A particular party may have no spy. To find the spy, if one exists, at a party, you are allowed to ask only one type of question—asking a guest whether they know a second guest. It is assumed that everyone answers your question truthfully.

If n guests attend the party, what is the maximum number of questions required to solve the problem for the worst case?

THEORY: The solution can be obtained by using the decrease-by-one algorithm to initially reduce the group of possible spy. If n = 1, that one person is a spy by definition. If n > 2, select two guests, say Alice and Bob. Ask Alice whether she knows Bob. If Alice does not know Bob, remove Alice from the group of possible spy. Otherwise, remove Bob from this group. Solve the problem recursively for the remaining group of n - 1 guests who can still be spy until only one guest is left in the group. Finally, in the worst case, you will then need to verify from all the guest at the party if the person left in the group is actually a spy.