问个数学难题

来源:百度知道 编辑:UC知道 时间:2024/05/18 02:57:06
21个人参加一项考试,试卷上共有15道是非题,已知对每2个人而言,至少有一道相同的题目这2人都答对了,问答对人数最多的题目最少有多少人回答正确。
要有过程,希望大家认真看清楚题目。

小柯西,你看错题目了吧。我来解决吧:
(1)设所求为n
每题至多n人答对,产生n(n-1)/2个对
15×n(n-1)/2 >实际的> 21*20/2
n(n-1)>32
n>5.xxxx
所以n>=6

(2)答案是7。
用反证法证明6不可能。如果每道题答对的人数至多为6,则这15题中至少有12题有6个人回答正确,否则有相同正确答题的学生对至多为11*C(6,2)+4*C(5,2)=205<C(21,2)=210。而且我们可以得到每个人至少答对4道题,否则这个人至多只能与3*5=15个人有相同的回答正确的题目。又由于5*21>6*15,故必有人恰好回答对了4道题,不妨设第一个人恰好回答对了4道题。这4道题必然有6个人答对,且除了第一个人,没有人同时回答对了这4题中的2题以上,否则与第一个人有相同的回答正确题目的人小于20个。不妨设回答对这4题的人分别为{1,2,3,4,5,6},{1,7,8,9,10,11},{1,12,13,14,15,16},{1,17,18,19,20,21}。除了这4题外,至少还有8道题有6人回答正确。对每道6人答对的题目,这6个人要么至少有3 个人落在上面4个集合中的同一个中,要么至少有2对2个人落在同一个集合中,不管怎样,至少有2对人有2道题以上答案一样正确,这样这8道题至少有16对人有2道题以上答案一样正确,这样一来,C(21,2)+16=226>15*C(6,2)=225,矛盾。

下面证明7是可能的,只要构造出例子来就行了,考虑一下这15个集合{1,2,3,4,5,6},{7,8,9,10,11,12},{1,2,7,8,13,14,15},{3,4,9,10,16,17,18},{5,6,11,12,19,20,21},{1,2,9,10,19,20,21},{3,4,11,12,13,14,15},{5,6,7,8,16,17,18},{1,2,11,12,16,17,18},{3,4,7,8,19,20,21},{5,6,9,10,13,14,15},{13,14,15,16,17,18},{16,17,18,19,20,21},{19,20,21,13,14,