2007-03-20

数学趣题:区分好人与坏人

问题:现有n个人,多于一半是好人,其余为坏人。你并不不知道他们具体谁是好人谁是坏人,然而他们彼此很清楚。
现在你每次可以挑两个人互相指认对方是好人还是坏人,好人总说实话,而坏人则会胡说(不一定是假话)。
请找到一个算法区分所有好人与坏人,并给出所需次数(大致数量级即可)

解答:(以下为大致阐述,对于细节,如是否严格大于或大于等于之类请自行讨论)
对于n较小的情况,如2,3,可以指定一个人T,让他与其余所有人互相指认,因为好人多于坏人,所以看结果是说T是好人的多还是坏人的多,那个多T就是哪个,如果一样多,T是好人。此时虽然是n平方数量级,但也可看作线性。

对n较大的情况,我们希望尽快找到一个好人以便指认出其余人的情况
把n个人两两分组(如有多余暂不考虑,放到下一轮处理),让他们互相指认。结果有如下几种情况:
a.至少一个人说对方是坏人
b.都说对方是好人

对于a, 组里至少一个人是坏人,我们把所有这样的组全部“淘汰”
对于b, 组里两个人必同为好人或同为坏人,我们在这样的组中每组任选一个淘汰。

这样一轮下来,可以知道淘汰掉的坏人不少于淘汰掉的好人,仔细分析还可知道剩下的人当中一定还是好人比坏人严格多。
这样下去直至剩下小于4人的情况,就可以用最开始的方法找到一个好人。
此时所花的次数约为N/2 + N/4 + ..., 大约等于N,然后再用至多N-1次指认就可以分辨所有好人与坏人了。

所以最后的数量级为2N
发表评论