诚实人和说谎者

今天我收到这样一则问题：n人中有诚实人和说谎者。诚实人永远说真话，而说谎者既可能说真话也可能说假话。有一种提问方式可以在不知道对方身份的情况下获得一些信息，那就是找两个人提问，问的内容是“对方是诚实人还是说谎者？”如果双方的回答都是“对方是诚实人”，那么真实的情况或者是双方都是诚实人，或者都是说谎者。如果得到其他的回答，那么只能确定至少有一人是说谎者。

为了进一步确定被调查者的身份，引入“高尚组”的定义：如果超过半数的人是诚实人，则称这一组人为“高尚组”。现在希望利用上述提问方式，做⌊n/2⌋次提问，并根据所获得的信息，找出一个新的“高尚组”，且人数不超过⌈n/2⌉。

我给出的解答如下：需要分情况讨论。

  1. n = 2m为偶数。这种情况下，做法如下：
  2. 将n人分为X, Y两组，每组m人，组员分别记作Xi, Yi(i = 1, 2, …, m)。
  3. 以(Xi, Yi)作为一对，提问，根据回答得到\[Q_i=\cases{1 & 当回答均为“对方是诚实人”时, \cr 0 & 其他.}\]
  4. 构造一个新的组{Xi | Qi ≠ 0}，即X组中对应双方均回答“对方是诚实人”的组员。
  5. n = 2m+1为奇数。做法如下：
  6. 将n人分为X, Y，每组m人，以及Z组1人。
  7. 同上。
  8. 同上。
  9. 当第3步构造的组的人数为偶数时，再将Z组的1人包含在内。

首先说明，因为X组的人数为\[\lfloor{n/2}\rfloor = \cases{\lceil{n/2}\rceil & $n$为偶数, \cr \lceil{n/2}\rceil - 1 & $n$为奇数, }\]因此构造的新的组人数一定不超过⌈n/2⌉。

然后证明按照上述方法构造的新组也是“高尚组”。对于被提问者，可以将其分成3类。

  1. 双方均为诚实人，设共有a对。
  2. 双方均为说谎者，设共有b对。
  3. 其他，设共有m-a-b组。

然后分情况讨论。

对于情况1，诚实人共有a+b+(m-a-b) = 2a+c = a-b+m人。根据“高尚组”的定义，需满足\[a-b+m \geq m+1 \quad\hbox{即}\quad a \geq b+1\] 意为A类多于B类。上述第3步排除了C类，保留了全部A类和部分B类。由此可知，构造的新组中，诚实人必多余说谎者，因此构成“高尚组”。

对于情况2，设\[z=\cases{1 & Z组的1人是诚实人, \cr 0 & Z组的1人是说谎者.}\]则诚实人共有a-b+m+z人。根据“高尚组”的定义，需满足\[a-b+m+z \geq m+1 \quad\hbox{即}\quad a \geq b+(1-z) \geq b\] 意为A类不少于B类。当构造出来的新组人数为偶数时，有两种可能性。

  1. 诚实人比说谎者多，那么两者相差至少2人，因此将Z组的1人包含进来不会造成问题。
  2. 诚实人和说谎者同样多，即a=b，则由上面的不等式得z≥1，说明Z组的1人一定是诚实人，因此将他包含进来可以使得构造出来的组成为“高尚组”。

当构造出来的新组人数为奇数时，经过推理可知，其中诚实人一定比说谎者多，所以这时候就没有必要把Z组的1人包含进来了。

由此可知，构造的新组中，诚实人多于说谎者，因此构成“高尚组”。

进一步的问题是，设计一种Θ(n)的算法，分辨出所有n个人的身份。

这个问题的前提是已知这个n个人构成“高尚组”。根据上面的步骤，我们可以用⌊n/2⌋次提问，将“高尚组”的人数降到不超过⌈n/2⌉人。把这样的操作称作一轮测试并设其用时为1。

假设n = 2m+k (0≤k<2m)，则只需不超过m轮测试就可以找出一个诚实人。这个过程的用时\[T_1(n) \leq \lfloor{n/2}\rfloor + \lfloor{n/4}\rfloor + \cdots + 1 \leq 2^{m-1} + 2^{m-2} + \cdots + 1 = 2^m \leq n.\]

找出一个诚实人后，只需不断地以他和其余n-1人作为一对进行提问，就可以知道所有人的身份。这个过程的用时显然为\[T_2(n) = n-1.\]综上所述，算法的总时间复杂度为\[T(n) = T_1(n)+T_2(n) = \Theta(n).\]

分享