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.
Solution Stats
Problem Comments
Solution Comments
Show commentsProblem Recent Solvers17
Suggested Problems
-
Number of 1s in the Binary Representation of a Number
442 Solvers
-
358 Solvers
-
438 Solvers
-
174 Solvers
-
Find out sum of all elements of given Matrix
497 Solvers
More from this Author18
Problem Tags
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!