诚实人和说谎者

诚实人和说谎者

Thu Feb 4, 2016

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

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

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

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

首先说明，因为X组的人数为为偶数为奇数⌊n/2⌋={⌈n/2⌉n为偶数,⌈n/2⌉−1n为奇数,因此构造的新的组人数一定不超过⌈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≥m+1即a≥b+1 意为A类多于B类。上述第3步排除了C类，保留了全部A类和部分B类。由此可知，构造的新组中，诚实人必多余说谎者，因此构成“高尚组”。

对于情况2，设组的人是诚实人组的人是说谎者z={1Z组的1人是诚实人,0Z组的1人是说谎者.则诚实人共有a-b+m+z人。根据“高尚组”的定义，需满足即a−b+m+z≥m+1即a≥b+(1−z)≥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轮测试就可以找出一个诚实人。这个过程的用时T1(n)≤⌊n/2⌋+⌊n/4⌋+⋯+1≤2m−1+2m−2+⋯+1=2m≤n.

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