算法导论的一道课后练习题,挺有意思

这个题目的题意是这样的:

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

 
这个题目我琢磨了半天,确实很巧妙,值的思考,我的证明如下:
记T=好人,F=坏人
那么两个人AB的指认结果可能为TT,TF,FT,FF。
TT对应的可能是A坏B坏,A好B好(两人都是坏人或者都是好人)
TF对应的可能是A坏B好,A坏B坏(A必然是坏人)
FT对应的可能是A好B坏,A坏B坏(B必然是坏人)
FF对应的可能是A坏B坏,A坏B好,A好B坏(一好一坏或者都坏)
先证明第二问,先假设N是偶数,一共是N/2对,让每对分别指认,如果结果是TT,那么两人或者都好或者都坏,随便留下一个人,如果结果是
TF或者FT,可以直接排除坏人剩下一个人,如果结果是FF,两人都不留下。这样经过这个过程后,剩下的人数<=N/2。
接下来证明这剩下的人中好人仍然比坏人多,由于FF两人都拿下,并且拿掉的坏人肯定>=好人,由于初始好人>坏人,所以除去FF对应的人里面好人还是比坏人多,假设回答TT的里面好人有n对,坏人m对,回答FT或TF的里面有好人的p对,都是坏人的z对,那么2n+p>2m+2z+p,得到n > m + z,按照前面的步骤淘汰后剩下的好人有n+p,坏人有m+z,因为n>m+z,所以n+p>m+z,好人比坏人多。
接下来看N是奇数的情况,同样按照上面的步骤比较,会剩下一个单独的人,假设我们剩下的是个好人,那么那n对中好人>=坏人,最后得到n+p>=m+z,再加上剩下的这个好人,n+p>m+z,好人比坏人多;如果我们剩下的是个坏人,那么n队中好人>坏人+1,依次计算下去,还是好人比坏人多。
第二问就此得到证明。
第三问的话就明显了,递归使用上述方法,N/2+N/4+N/8...=theta(N)
第一问,坏人可以采取如下策略,碰到好人就说坏人,碰到坏人就说好人。这样坏人要么和好人一块被淘汰掉,要么混淆两个好人,没有确定的方法可以确保我能找到好人,只能看运气。
原文地址:https://www.cnblogs.com/marsbible/p/3340877.html