算法导论题解: 4-6 VLSI Chip Testing

前几天面试的时候被问到一个涉及Master Theorem的题，于是今天把算法导论重新拿出来看了一下，发现了这道很有趣的题，以前居然没有注意。最近智商下降得厉害，想了N久才做出来，若有错请指出。

有N个人，分为好人和坏人两种，每次你可以挑两个人出来让他们互相指识彼此是好还是坏。好人一定说实话，坏人会乱说。现在你要从他们里面找出一个肯定是好人的。一共有三问：(1)证明若好人数目不超过N/2，则坏人们总可以通过故意捣乱，让你找不出正确答案。(2)证明若好人数大于N/2，存在一种方法可以通过floor(N/2)次判断使问题规模缩小到最多只有原来的一半。(3)证明若好人数大于N/2，可以用theta(N)次判断找出一个好人。

实际上问题的提示很强了，大致思路就是每次把问题缩小一半而已。

首先我们把情况列一下：如果两人互称对方是好人，那么两人同好或同坏；如果A说B好但B说A坏，那么A一定是坏人，B的好坏未知；如果两人互称对方是坏人，那么两人中至少有一个坏人。

首先我们试图证明第2问。因为好人比坏人多，所以我们是不怕“同归于尽”的，于是方法如下：把N个人任意两两组对，组成floor(n/2)对，如果是奇数的话就余出一个人。让他们互相指认，如果两人互称对方好人，随便挑其中一个杀掉；如果两人互称对方坏人，两个全杀掉；如果A称B好人但B称A坏人，把A杀掉。这样会发现人数至少缩小了一半，下面就是要证明剩下的人里仍然是好人占多数。

下面先考虑N是偶数的情况，此时一共组成了N/2对，每一对无外乎是好人遇好人，好人遇坏人，坏人遇坏人三种情况。设好人遇好人的有a对，好人遇坏人的有b对，坏人遇坏人的有c对，那么好人一共有2a+b个，坏人共有2c+b个。因为好人多，所以有2a+b>2c+b，即a>c。

如果我按照上面的规则杀人，那么当好人遇到坏人时，坏人应该说对方是坏人，这样还可以拼个同归于尽，不然他就白死了。当坏人遇到坏人时，两个坏人不管怎么说也至少要死一个。当好人遇到好人时，两个好人也要死一个。也就是说，如果坏人采取最佳策略，那么好人会死a+b个，坏人会死c+b个，于是好人还剩a个，坏人还剩c个，由前面已得a>c，所以剩下的还是好人多。

如果N是奇数，情况会复杂一些。此时有一个人会余出来，我们把这个余出来的人放在一旁观战。如果以后又出现了奇数个人，再让余出来的人替换掉原来观战的人。如果最后场上剩了一人（不管有没人观战），那个人就是好人。如果最后场上没人了，这时一定有人观战，观战的那个就是好人。这个方法的正确性在于，在任一时刻，如果场上好人和坏人数相同，观战的必然是好人。如果观战的是坏人，场上好人数必大于坏人数。（证明留给读者;p）

可见每轮过后最多剩下一半的人，所以第2问得证。然后第3问也就显然了，因为N+N/2+N/4+… = theta(N)

最后说一下第一问，如果坏人不比好人少，设好人有x个，坏人有y个且y>=x，那么我们可以让其中的x个坏人伪装好人。具体来讲，设好人集合为A，假好人集合为B，剩下的坏人为C（可以为空集），我们知道A集合里的人会说A集合里的人好，会说B,C都坏。坏人们可以商量好了让B集合的人都说B好，说A,C坏，让C说A,B都坏（或者都好）。这样你就无法区分A,B集合到底谁好谁坏了，因为他们的表现是完全一样的。