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

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

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

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

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

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

所以最后的数量级为2N