今天看了一篇博客，說的是導論的一道課后題以及博主的解答，感覺對邏輯思維的鍛煉還是很有價值的，特意引用一下。這個題目的題意是這樣的：

　　有N個人，分為好人和壞人兩種，每次你可以挑兩個人出來讓他們互相指識彼此是好還是壞。好人一定說實話，壞人會亂說。現在你要從他們里面找出一個肯定是好人的。一共有三問：(1)證明若好人數目不超過N/2，則壞人們總可以通過故意搗亂，讓你找不出正確答案。(2)證明若好人數大于N/2，存在一種方法可以通過floor(N/2)次判斷使問題規?？s小到最多只有原來的一半。(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/xuekai-to-sharp/p/3341377.html

總結

以上是生活随笔為你收集整理的一道有意思的导论问题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。