Problem 44708. Sherlock Holmes: The Spy Problem

Created by J. S. Kowontan

Solve Later

{"relationships":[{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/document","targetMode":"","relationshipId":"rId1","target":"/matlab/document.xml"},{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/output","targetMode":"","relationshipId":"rId2","target":"/matlab/output.xml"}],"parts":[{"partUri":"/matlab/document.xml","relationship":[],"contentType":"application/vnd.mathworks.matlab.code.document+xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\"?>\n<w:document xmlns:w=\"http://schemas.openxmlformats.org/wordprocessingml/2006/main\"><w:body><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>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.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>If</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>n</w:t></w:r><w:r><w:t> guests attend the party, what is the maximum number of questions required to solve the problem for the </w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:b/></w:rPr><w:t>worst case</w:t></w:r><w:r><w:t>?</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>THEORY:</w:t></w:r><w:r><w:t> The solution can be obtained by using the decrease-by-one algorithm to initially reduce the group of possible spy. If</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>n</w:t></w:r><w:r><w:t> = 1, that one person is a spy by definition. If</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>n</w:t></w:r><w:r><w:t> &gt; 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</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>n - 1</w:t></w:r><w:r><w:t> guests who can still be spy until only one guest is left in the group. Finally, in the</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:b/></w:rPr><w:t>worst case</w:t></w:r><w:r><w:t>, you will then need to verify from all the guest at the party if the person left in the group is actually a spy.</w:t></w:r></w:p></w:body></w:document>"},{"partUri":"/matlab/output.xml","contentType":"text/xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\" ?><embeddedOutputs><metaData><evaluationState>manual</evaluationState><layoutState>code</layoutState><outputStatus>ready</outputStatus></metaData><outputArray type=\"array\"/><regionArray type=\"array\"/></embeddedOutputs>"}]}

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 &gt; 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.

Solve

Solution Stats

13 Solutions
8 Solvers

Last Solution submitted on Apr 12, 2020

Last 200 Solutions

Problem Recent Solvers8

Problem Tags

decrease-by-one spy

Problem 44708. Sherlock Holmes: The Spy Problem

Solution Stats

Last 200 Solutions

Problem Recent Solvers8

Suggested Problems

More from this Author18

Problem Tags

Problem 44708. Sherlock Holmes: The Spy Problem

Solution Stats

Last 200 Solutions

Problem Recent Solvers8

Suggested Problems

More from this Author18

Problem Tags

Players