Question

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

Answer 1

【答案】7

【解析】

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

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

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

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

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

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

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

由柯西不等式有.

所以，.

解得.

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

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

綜上，該代表隊(duì)至少有7名選手