返回题库

反恐精英

Counter Strike

专题
Brainteaser / 脑筋急转弯
难度
L6

题目详情

NN 名卧底特工在黑帮老巢中被发现。其中不到一半是恐怖分子，其余都是反恐人员。由于他们的工作极其保密，没有任何证据能证明谁是谁。不过，因为他们曾经组队行动，所以每个人都知道谁是真正的恐怖分子、谁是反恐人员。

一次询问的形式是：问第 ii 个人“第 jj 个人是不是反恐人员？”反恐人员一定说真话，而恐怖分子可能会撒谎来混淆视听。要找出一名反恐人员，最少需要多少次询问？

NN undercover agents have been found in don's lair. Less than half of them are terrorists and the rest are anti-terrorists. The nature of their job is so secret that there is no proof whatsoever to testify who is who. However, each of them knows who was the actual terrorist and who was the anti-terrorist because they worked in teams.

A query consists of asking person ii if person jj is anti. Anti will always speak truth but a terrorist may lie to confuse you. What is the fewest number of queries required to find the anti?

解析
题意：\text{题意：}
  • 有 NN 名特工，其中不到一半是恐怖分子，其余是反恐人员，因此反恐人员占严格多数。
  • 一次询问是：问特工 ii，特工 jj 是否是反恐人员。反恐人员总是说真话，恐怖分子可能撒谎。
  • 目标：用尽可能少的询问找出至少一名反恐人员。
解法：\text{解法：} 第 1 步：利用多数性质\text{第 1 步：利用多数性质}
  • 反恐人员构成严格多数。
  • 因此，任何利用“多数保留”思想的方法最终都会留下一个反恐人员。
第 2 步：候选人策略（类似 Boyer–Moore）\text{第 2 步：候选人策略（类似 Boyer–Moore）}
  1. 先任意选一个候选特工 CC。
  2. 对每个其他特工 AiA_i，询问：“CC 是反恐人员吗？”
    • 如果回答是，就保留当前候选人，继续。
    • 如果回答否，就丢弃当前候选人，并把 AiA_i 设为新的候选人。
  3. 当你问完其余 N−1N-1 个人后，最后剩下的候选人一定是一名反恐人员。
第 3 步：最少询问次数\text{第 3 步：最少询问次数}
  • 我们需要把候选人与其他每个人都比较一次，因此共需要 N−1N-1 次询问。
  • 这是最优的，因为在最坏情况下，由于恐怖分子可能撒谎，每一次询问都可能是必要的。
N−1 次询问\boxed{N-1 \text{ 次询问}}

Original Explanation

Problem:\text{Problem:}
  • NN agents, less than half are terrorists, rest are anti-terrorists (majority).
  • Query: Ask agent ii if agent jj is anti. Anti always tells the truth, terrorists may lie.
  • Goal: Find at least one anti-terrorist with fewest queries.
Solution:\text{Solution:} Step 1: Majority property\text{Step 1: Majority property}
  • Anti-terrorists form a strict majority.
  • Any “majority vote” among agents will indicate an anti.
Step 2: Candidate strategy (Boyer–Moore analogy)\text{Step 2: Candidate strategy (Boyer–Moore analogy)}
  1. Pick an initial candidate agent CC.
  2. For each other agent AiA_i, ask: "Is CC anti?"
    • If answer is yes, keep candidate and continue.
    • If answer is no, discard candidate, pick AiA_i as new candidate.
  3. After querying all N−1N-1 other agents, the remaining candidate is guaranteed to be an anti.
Step 3: Minimal number of queries\text{Step 3: Minimal number of queries}
  • We need to query the candidate against every other agent: N−1N-1 queries.
  • This is optimal because in the worst case each query is necessary due to possible lies from terrorists.
N−1 queries\boxed{N-1 \text{ queries}}