好人与坏人

Source: An exercise class of Theoretical Computer Science

Description:
Suppose there are some guys, some of which are good and the others are bad. Good guys always tell the truth, whereas bad guys can tell truth or lie, depends on their wish. We know the good guys are more than the bad guys. Each time we can ask a guy that whether another guy is a good guy.
The question is how to determine the good guys in minimum queries.


Solution: (in Chinese for clarity)
把这n个人两两配对（n为奇数时剩下一个），让每一对人分别说对方是不是好人。那么把都说对方是好人的对留下，别的对去掉。则留下的对中要么都是好人，要么都是坏人；去掉的每一对里一定是一个好人和一个坏人，于是去掉的好人和坏人一样多，剩下的好人还是比坏人多。然后看n为奇数时落单的一个人怎么处理：
1. 如果留下的对数为奇数，则好人对必比坏人对多。把落单的一个人去掉，再从这奇数对中每对取出一个人组成新的集合。这个集合里的好人比坏人多，于是形成了一个子问题。
2. 如果留下的对数为偶数，则如果好人对和坏人队一样多，那么落单的一定是好人。如果好人对比坏人对多，那么无法确定落单的是好人还是坏人。从这偶数对中每对取出一人，再加上落单的那个人，组成新的集合，则集合里好人比坏人多（想想为什么）。于是也形成了一个子问题。
应用同样的算法，最后必剩下一个好人。再用这个好人确定其他所有人。总共询问次数最坏不超过2n。