對網傳一道詭異的邏輯問題的解答表示強烈質疑！？

12-11

100個人回答五道題，有81人答對第一題，91人答對第二題，85人答對第三題，79人答對第四題，74人答對第五題，答對三道題或三道題以上的人算及格，那麼，在這100人中，至少有多少人及格？

這道題目的解答隨便可以百度得到，解答無非是以下這樣:
問至少有多少人及格，那就是說不及格的人數最多時及格的人數最少．100人回答5道題，相當於做500道題，共答對的題目數量有：81+91+85+79+74=410（道），則出錯的數量有：500-410=90（道），錯3道以上就不及格，每人錯3道時不及格人數最多，90÷3=30（人），則及格的人數是：100-30=70（人）．

該回答的邏輯看起來機智又簡潔。但細想起來有重大的缺陷。
現舉一反證說明:假設還是五道題，100人。但這次答對第一題的有十個人，其他四個題所有人全部答對。那麼答錯的總題目數還是90道。按照百度上的思路，得到的結論應該同樣是70人。然而很明顯，在新的條件下，所有人都合格了。
針對這一類反例，請問各位大神有什麼見解？問題出在哪裡？

這只是一個常見的組合問題的邏輯
一個組合極值問題一般而言分兩部分，證明和構造
以這道題為例，原解答負責給出最小值的一個下界估計(最小值不小於70)，而再構造一個能取到70的例子(最小值不大於70)，這樣就證明了最小值確為70。
接下來構造一個取到最值70的情況，為了方便敘述，用數學語言描述:
設A={1,2,...,100}
B1,B2,B3,B4,B5為A的五個子集，且
|B1|=81,|B2|=91,|B3|=85,|B4|=79,|B5|=74
令f(i)=|Ci|，其中Ci={Bj|i∈Bj,j=1,2,3,4,5}，i=1,2,...,100
只需構造B1,B2,B3,B4,B5，使得:
使得f(i)≥3的i有且只有70個，不妨設為31,32,...,100
注意到此時必有i=1,2,...,30時，f(i)=2
構造:
B1={20,21,...,100}
B2={1,2,...,19,29,30,...,100}
B3={14,15,...,28,31,32,...,100}
B4={5,6,...,13,31,32,...,100}
B5={1,2,3,4,31,32,...,100}
這樣就完成了證明.
構造的思路並不困難。把1,2,...,30排成一列，用五種顏色的圓圈分別表示B1,B2,B3,B4,B5所未取到的數，我們希望:
①每個數上有且只有3個圈
②每個數上沒有相同顏色的圈
於是自然地按照順序排列，由於沒有一個Bj的元素數目不多於70，因此②是一定能滿足的。如圖所示:

至於為什麼題主及一些答主認為這是錯誤的並舉出的所謂反例，這些只是反駁了證明過程本身，然而只有證明過程是不夠的，還要結合構造。證明和構造加起來才構成了嚴謹的邏輯，單獨拿出來任何一部分進行推敲，得到的結果必然是邏輯不嚴謹。因此，對於所謂的反例，這個證明過程並不適用(對於那個錯題而言更是如此)，題目敘述變時如果極值變化了，那麼就無法構造出原有的證明對應的結果，就要放縮地更緊而求出新的最值。

解了個下界，但沒有解出下確界

這是一種最理想的情況，如果可以加一個構造，證明是可行的，

補上構造（不唯一）
第一題，1號到19號答錯
81人正確
第二題，20號到28號答錯
91人正確
第三題，1號到9號答錯，25號到30號答錯
85人正確
第四題，10號到30號答錯
79人正確
第五題，1號到24號答錯，29和30號答錯
74人正確

從始至終，只有前三十個倒霉蛋做錯了題，而且每個人恰錯了三題，所以有70個人及格的情況可以出現。

如果把構造中的60個錯題（前三十個人每人減少兩個）改到後70個人均攤的話，可以做到100個人全部及格╮（╯＿╰）╭皆大歡喜。

這個解答是有問題的，雖然答案是對的。

問至少有多少人及格，那就是說不及格的人數最多時及格的人數最少．100人回答5道題，相當於做500道題，共答對的題目數量有：81+91+85+79+74=410（道），則出錯的數量有：500-410=90（道），錯3道以上就不及格，每人錯3道時不及格人數最多，90÷3=30（人），則及格的人數是：100-30=70（人）．

「每人錯3道時不及格人數最多」基於這個結論，只能證明答案大於等於70，而不能證明答案等於70。

為了證明答案等於70，我們可以構造一組答案為70的方案（設所有人編號1,2,...,100）：

第一題：[1,81]

第二題：[1,72],[82,100]

第三題：[1,70],[73,87]

第四題：[1,70],[88,96]

第五題：[1,70],[97,100]

這樣[1,70]這70個人全部及格，也就證明了答案等於70。

當然這種演算法並不正確，因為當我們把數字改掉之後，就不能得到正確結果了。反例：如果5道題的通過人數分別為20,30,70,80,90，由該演算法得到的答案為30，實際答案為40。

本人想的一種演算法是這樣的：用 $a_i$ 表示第 $i$ 題的答對人數，考慮判斷能否使至少有 $100-x$ 人不及格（這些人的集合記為 $B={b_0,b_1,cdots,b_{99-x}}$ ，其餘人記為 $A$ ），為保證最優性，當 $a_ile x$ 時總是可以只讓 $A$ 中的人答對第 $i$ 題，否則總是可以讓所有 $A$ 中的人均答對第 $i$ 題， $B$ 中 $a_i-x$ 人答對第 $i$ 題。由抽屜原理，當 $sum_{i=1}^5max{a_i-x,0}>2(100-x)$ 時一定不可行。

當 $sum_{i=1}^5max{a_i-x,0}le 2(100-x)$ 時，對於第 $i$ 題，令 $B$ 中答對該題的人的集合為

${b_{jmod(100-x)}|jinmathbf{N^*},sum_{k=1}^{i-1}max{a_k-x,0}le j<sum_{k=1}^{i}max{a_k-x,0}}$

即可。所以能夠不超過 $x$ 人及格的條件是 $sum_{i=1}^5max{a_i-x,0}le 2(100-x)$ 。用二分法求出最小的滿足條件的 $x$ 即可。

我認為這個問題不是那麼簡單。同時我想出了一種演算法，用貪心策略解出這個人數同樣也是70人。現描述如下(該演算法的直觀解釋放在了倒數第二段):
首先，跟百度到的解答思路一樣，錯3道以上就不及格，每人錯3道時不及格人數最多，所以應當限定不及格者只錯三道，這一點是確鑿無疑的。
接下來，我們就把每道題出錯的人數進行分配，分配數組為(19.9.15.21.26)。
接下來，每次選取五道題中錯題人數最多的三道，將該人數減一(比如在該例中，選最大的三個數是19.21.26,分別減一之後變為18.20.25，之後錯題人數更新為(18.9.15.20.25))重複該步驟，直至有三列變為0終止，那麼迭代的次數就是不及格人數的最大值(程序很簡單，幾行代碼就可以出來，並得出結果為30，那麼合格的人數自然為70)。姑且把這個演算法命名為X演算法。
X演算法正確性的證明:
用第二類歸納:若最少的三列對應的人數之和為1時時，演算法顯然正確，即得到的分配方案能使得不及格人數最多。
假設當最少的三列對應的人數之和為1~k時X演算法也成立。那麼當和為k+1時，用反證法:若不按照X演算法的規定，而是從最小跟次小的堆中也進行了減一操作，那麼由於最少三列的和一定不超過k，可按照假設進行處理，此時的減一操作可以看成是把最小兩堆的數據拿到最大兩堆後，再按照X演算法的描述進行操作。易證明X演算法終止時，任何時刻數量最少的三組一定都變為零，所以任何步驟之後的迭代次數正是當前該最小三組的和。這說明按照X演算法描述所能分配的人數(即迭代的次數)一定是最多的。
這就證明了k+1時也成立。
綜上，該演算法對所有的n都成立。演算法的正確性得證。
直觀解釋:之所以稱之為貪心策略，是因為每一步我們都企圖讓迭代次數(即不及格的人數)最大化:因為迭代終止的條件是三列降為0，所以我們就企圖使得數目最少的三列減小的速度最慢，因而我們優先從最大的三組中選取。
請各位指出這個演算法的漏洞(如果有的話)，另外，這個演算法會不會是已經存在的某種演算法的變體？恕在下孤陋寡聞，願聞其詳！

首先瀉藥（雖然沒人邀我）。其他答案中各大神已經提到過，題主說的網上那種演算法答案是對的。但個人覺得應該是只適用於此題的，廣泛性不夠。可以舉個栗子來說明:

我們假設還是5道題，100個人，第一題100人做對，第二題100人，3、4、5題都是0人（大概是壓軸題的原因）還是三道及以上及格。按照網上演算法，應該是一共做對500-300=200道題，最多200÷3=66餘2即66人及格。

但是反觀我們假設的數據，3、4、5題無人做對，這已經足夠我們判斷沒人及格了，所以上面算出的66顯然是錯的。

那麼問題在哪呢？這個我就說不好了（語文不好），只可意會不可言傳，相信大家也都能體會出來（好像其他答案里有分析）。

題主給的題這樣算之所以對，是因為題目中所給最小數據（74）大於算出來的數據（70），而我舉的栗子中0小於算出來的66。

綜上，這種演算法應當再加上一個判別:最小數據和所算得數據中的最小值即為正確答案。

PS: 本人能力有限，不足之處也請各dalao指正。華老先生說過，我們要班門弄斧。

演算法是錯的，因為大部分情況是無法做到30個人每人勻分3道錯題的(從5道題共90個錯題中，每題取一個，3個不同的錯題組成一組，算作一個不及格的人)，不過本題給的數據比較巧，所以答案是對的。

我想了一個比較笨的演算法，可以驗證能不能勻分。

五道題錯的數量從小到大排列之後分別為9,15,19,21,26，從錯的最多的三道題中，即19,21,26中取六組(即六個不及格的人，每個人錯的都是這三道題)，使原本錯第二多的題數剩下的數據能和第四多的相等，這樣取六組數之後剩下的就是9,15,13,15,20，其中第三道題和第五道題分別減去第一道題錯的數，差之和正好是15，所以可以用二四兩道題加上差之和組成15組，剩下的135三道題每道剩了9個，組成9組，一共是30組，所以是正好可以勻分的，答案是對的。

用排列組合做，回去給答案，目測給出的答案不對

這不是集合的問題么？高中數學、概率論應該都討論過類似的問題，這裡不過複雜了一些。解答顯然是有問題的。

贊同 @rsa
其實粗略的看了他的回答
第一遍沒看懂（因為看的是真粗略）
然後就太長不看了
然後自己解了一遍
再看第二遍就秒懂了
或許是不喜歡冷冰冰的專業答題方式吧
（或許我才是冷冰冰的那個）
或許是高數經常掛科以至於討厭太多的符號吧
我更喜歡以初中生的方式解決此題
以提供給像我一樣討厭高數的人來理解此題

容我畫幾個圖先

賓館沒草紙還是算了吧

等我假期high夠了回去再更……

這個解答粗看起來就有重大缺陷好不。。。

題目說「81人答對第1題，91人答對第2題」，好，我們把這句話換成「71人答對第1題，101人答對第2題」。然後你會發現百度中的那個解法可以完全不改的用上，並得出同樣答案。

這說明什麼？這說明該解法與「具體有多少人答對某個題」無關，只與這5個數字加起來的和（410）有關。

原解答錯在哪呢？錯在「每人錯3道時不及格人數最多」這一句，這句構造了「每人錯3道，而沒有人錯1道或者2道」這一特殊情況，你還需要證明這個情況與題目中那些「81人答對第1題，91人答對第2題」之類的條件不衝突，換句話說，這個情況要真的能構造出來。

原解答的漏洞就在於缺少這個證明。即使答案數字有可能是對的。

我認為你是對的