Question

【題目】最近的一次數(shù)學(xué)競賽共6道試題，每題答對得7分，答錯(或不答)得0分.賽后某參賽代表隊獲團體總分161分，且統(tǒng)計分數(shù)時發(fā)現(xiàn)：該隊任兩名選手至多答對兩道相同的題目.沒有三名選手都答對兩道相同的題目.試問該隊選手至少有多少人？

Answer 1

【答案】7

【解析】

設(shè)該隊有n名選手，分別記為，記6道題的編號依次為1,2,...,6.以編號為行、選手為列作一個6×n的方格表.如果選手答對第j(j=1,2,...,6)題，就將方格表中第j行第i列的小方格(j, i)的中心染成紅點.我們的問題就是在6×n的方格表中，不存在“橫”6點矩形和“縱”6點矩形的情況，且至少有23個紅點時，求n的最小值.

如第1列有6個紅點，那么，后面各列至多有2個紅點.因為，于是，取第2至10列，其中第2至9列每列有2個紅點，第10列1個紅點(如圖)滿足題設(shè).這說明n的最小值不大于10.

我們發(fā)現(xiàn)，可通過將第1列中某點移到此點所在行的其他列中來減少圖6的列數(shù)，如作移動(6, 1)→(6,2)，可同時作移動(4,10)→(6,3)，(3,9)→(6,4)，(5,9)→(6,7)，這樣便得到有23個紅點的圖7.類似地可得圖8.這說明n的最小值不大于7.

下面證明：n的最小值大于6.

對于一個恰有6列的方格表，由抽屜原理知至少有一列紅點數(shù)不少于4，不妨設(shè)第1列，且第1列的前4行的小方格的中心是紅點.如果某列有2個紅點，則稱其為某列上的一個紅點“行對”.這樣在前4行中，除第1列外的5列中每列只能有一個行對.于是，前4行中總共有個行對.考慮最后兩行：若第1列還有紅點，那么，有紅點的這一行不能再有其他的紅點.如第1列還有2個紅點，這時能增加9個行對，6×6方格表中共有11+9=20個行對；如第1 列還有1個紅點，不妨設(shè)第1列第5行的小方格有紅點，這時即使第6行除第1列外的其他小方格都有紅點，那么，可增加個行對，6×6方格表中共有11+14=25個行對；如第1列沒有其他的紅點，那么，在最后兩行中最多還有兩個行對，這兩個行對占去了兩列，在余下的三列中，每列最多有1個紅點，于是，可增加行對2×5+3×2=16個，這時，6×6方格表中最多有11+16=27個行對.這說明27是可能的行對總數(shù)的最大值.

設(shè)第i列的紅點數(shù)為，

且.則所有行對的總數(shù)，即.

由柯西不等式有.

所以，.

解得.

由k為正整數(shù)知k≤21.這說明6×6方格表中紅點個數(shù)最多為21個.

又當(dāng)n≤5時，方格表中紅點總數(shù)不大于4×5=20個.這說明n的最小值不小于7.

綜上，該代表隊至少有7名選手