Diogenes 教授有n个被认为是完全相同的VLSI芯片,原则上它们是可以互相测试的.教授的测试装置一次可测试二片,当该装置中放有两片芯片时,每一片就对另一片作
测试并报告其好坏.一个好的芯片总能够正确的报告另一片的好坏,但一个坏的芯片的结果就是不可靠的.这样,每次的测试的四种可能结果如下:
a)证明若少于 n/2 的芯片是坏的,在这种成对测试方式下,使用任何策略都不能确定哪个芯片是好的.
b)假设有多于 n/2 的芯片是好的,考虑从 n 片中找出一片好芯片的问题.证明 n/2 对测试就足以使问题的规模降至近原来的一半.
c)假设有多于 n/2 的芯片是好的,证明好的芯片可用 sita(n) 对测试找出.
解：
a）这是显然的了，找个反例就行了。
b）分情况考虑
(1)n为偶数
随机的两两配对，则共有n/2对，分别测试。考虑其中一对的测试结果：如果一好一坏，或者两坏，那么把这对丢弃。这样丢弃不难发现丢弃的好芯片数一定不大于丢弃的坏的芯片数；如果两好（实际情况是两个都是真的好或者两个都是真的坏），那么随意丢弃其中一个，留下一个。
这样操作后，留下的好的芯片数一定还是大于坏的芯片数的。分析：因为n为偶数，设好的芯片数为a，坏的芯片数为b， 则a-b>=2，由鸽巢原理，必然有一对好的相遇。再往下分析，如果有k对坏的相遇，那么至少再有k对好的相遇，所以两个好相遇的对数一定大于两个坏的相遇的对数。
这样原问题的规模降低一半。
(2)n为奇数
这个稍微复杂一点。还是随机两两分对，结果必然留下一个没有配对的。同样，结果为一坏一好或者两坏的，直接把这对扔掉，不影响后续判断，现在剩下的对都是两好的，这样对数设为m（如果m=0，则没有配对的那个必然是好的，结束，所以现在假设m不为0），真正两个好的对数设为a，真正两个坏的对数设为b，则a+b=m。
i) 如果m为奇数
不难得到a>b，我们可以把那个没有配对的那个扔掉，而直接考虑从这m对中每对任选一个，剩 下的都丢弃。这样需要考虑的有m个芯片，而且其中好的一定多于坏的。
ii)如果m为偶数
我们也从m对中，每对中任选一个，这样有m个芯片，再加上刚才没有配对的那个，我们考虑这 m+1个芯片即可。需要证明的是，这m+1个芯片中好的一定多于坏的：如果没有配对的那个是好的， 可以得到a>=b，结论没问题；如果没有配对的那个是坏的，并且m是偶数，所以a>=b+2，我们把这个 坏的就算留下也没有关系，好的还是多于坏的（必须要留下，因为我们不知道没有配对的那个是好的 还是坏的，我们只是证明把最后没有配对的这个留下是没有问题的）。
这样我们就证完了。
c) 按照b中的方法 T(n)<=T(n/2)+n/2 根据主定理推出T(n)=O(n)