牛油果蔬菜沙拉的做法:问个数学难题

小柯西,你看错题目了吧。我来解决吧：
（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,15},以及空集，检验发现每题之多7人答对，且每2人之间都有相同的正确答对的题目.

顺便说一下，这道题你可以去水木清华bbs的“智力乐园”版去看，里面有这道题的讨论。

3人

用点对点的方法做 把21各学生当作21个点列成一排

把15道题当作15个点列成一排

已知对每2个人而言，至少有一道相同的题目这2人都答对
所以每两个点（学生）要连向另一个点（题目）

21除以2余1，1+2=3

（听不懂的话发消息给我，本人初二，能力不强，纯属卖弄）

答案是6。

本题的实质是：对于21个结点的完全图，用15个完全图去覆盖，求其中最大的完全图的结点数最少是多少？

21个结点的完全图是210条边，如果照平均了算，15个完全图每个要分到14条边，而不少于14条边的最小完全图是6个结点15条

边的，所以6是一个下界，这时候有15条边可以共用，然而6是不是足够了呢？

n个结点的图可以用n阶“关系矩阵”表示，其矩阵元A(i,j)为第i,j两点间的边数，本题是无向完全图，所以可用值都为1的上

三角矩阵表示，其它的值我们无害的把它们定为零。

需要注意的是：矩阵的行与列是可以交换的，只需保证：号码相的行与列同时进行交换就可以了，而且每一个点都可以独立的

换成由其关于i=j的对称点表示，特别是也可以用下三角矩阵，这是为了做题的方便。

我们现在试着用6X6矩阵（如下）去覆盖21X21矩阵
零□●●●●●
一□□●●●●
二□□□●●●
三□□□□●●
四□□□□□●
五□□□□□□

我们得到一结果：

零零一二三四五六七八九十一二三四五六七八九十
零□●●●●●○●●●●●○●●●☆☆○○○
一□□●●●●○○●●●●○○●●●☆○○○
二□□□●●●○○○●●●○○○●★★☆☆☆
三□□□□●●○○○○●●○○○○●★●☆☆
四□□□□□●○○○○○●○○○○○☆●●☆
五□□□□□□●●●●●○●●●●●○○●●
六□□□□□□□●●●●○○●●●●○○○●
七□□□□□□□□●●●○○○●●●○○○○
八□□□□□□□□□●●○○○○●◇○○○○◆
九□□□□□□□□□□●○○○○○★●●●●
十□□□□□□□□□□□●●●●●○●●●●
一□□□□□□□□□□□□●●●●○○●●●
二□□□□□□□□□□□□□●●●○○○●●
三□□□□□□□□□□□□□□●●○○○○●
四□□□□□□□□□□□□□□□●○○○○○
五□□□□□□□□□□□□□□□□●●●●●
六□□□□□□□□□□□□□□□□□●●●●
七□□□□□□□□□□□□□□□□□□●●●
八□□□□□□□□□□□□□□□□□□□●●
九□□□□□□□□□□□□□□□□□□□□●
十□□□□□□□□□□□□□□□□□□□□□

●○表示用于覆盖的矩阵元
★☆表示重复覆盖的矩阵元
◆这个可以移动到前面◇处

用类似排三角形的方法可以简单的发现：16个6结点的完全图、4个11结点的完全图或9个8结点的完全图就可以对付21个结点的

完全图。而像本题的答案:15个6结点的完全图则需要作如上面比较具体的尝试才能得到。
---------------------------------------------------------------------------------------------------------------
现推广为：对于n个结点的完全图，用m个完全图去覆盖，求其中最大的完全图的结点数最少是多少？

记这个函数为f(n,m)(n,m=2,3,...)可知：
f(n,m)=1 m≥n时，f(n,1)=n，f(n,2)=n，f(n,3)=?

把完全图用关系矩阵表示出来，同样用前面的方法，可以简单的发现：

2k+1结点的完全图，一定可以用4个k+1结点的完全图覆盖，
3k+1结点的完全图，一定可以用9个k+1结点的完全图覆盖，
......
ik+1结点的完全图，一定可以用i^2个k+1结点的完全图覆盖。
......

由平均条件：f(n,m)=k k满足：mC(k,2)≥C(n,2) 即：k(k-1)≥n(n-1)/m 得k≥1/2+sqr(n(n-1)/m+1/4)

由关系矩陈得到的一个特殊解得到：f(n,m)≤{n/[sqr(m)]} []表示取下整，{}表示取上整

即：1/2+sqr(n(n-1)/m+1/4)≤f(n,m)＜n/[sqr(m)]+1

当n非常大时，两边都趋近于：n/sqr(m)+1，这说明能落在其中的结点数不会太多，具体结果，可以尝试解决。

但每种情况下，是不是都能很简单的像这样不拆开三角点阵就能解决呢？

[21*（21-20）]/2=210 210/15=14 故问答对人数最多的题目最少有14人回答正确（这里要用到排列分布）

N人

50