對網傳一道詭異的邏輯問題的解答表示強烈質疑!?
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。
本人想的一種演算法是這樣的:用 表示第
題的答對人數,考慮判斷能否使至少有
人不及格(這些人的集合記為
,其餘人記為
),為保證最優性,當
時總是可以只讓
中的人答對第
題,否則總是可以讓所有
中的人均答對第
題,
中
人答對第
題。由抽屜原理,當
時一定不可行。
當 時,對於第
題,令
中答對該題的人的集合為
即可。所以能夠不超過 人及格的條件是
。用二分法求出最小的滿足條件的
即可。
我認為這個問題不是那麼簡單。同時我想出了一種演算法,用貪心策略解出這個人數同樣也是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題」之類的條件不衝突,換句話說,這個情況要真的能構造出來。
原解答的漏洞就在於缺少這個證明。即使答案數字有可能是對的。
我認為你是對的
推薦閱讀:
※DES 演算法的設計思路是什麼?
※有關餘數的簡單方法,不知道是新發現還是已知?
※初級程序員,該如何提高?
※理論上可以通過除窮舉法以外的方法破解不可逆的加密演算法嗎?
※毒酒迷題:現有 1024 瓶美酒,其中 2 瓶有毒。毒藥 24 小時內發作,現有 65 名死囚,怎樣能在 24 小時 01 分內找出 2 瓶毒酒?