Question

【題目】某公司印制了一批文化衫，每件文化衫可有紅、黃、藍三種不同的顏色和四種不同的圖案.現(xiàn)將這批文化衫分發(fā)給名新員工，每名員工恰好分到圖案不同的4件.試求的最小值，使得總存在兩個人，他們所分到的某兩種圖案的4件文化衫的顏色全部相同.

Answer 1

【答案】19

【解析】

的最小值為19.

當時，表1所示的答題情形不符合要求.

表1

p>

（1）

（2）

（3）

（4）

【注】表l中（1）、（2）、（3）、（4）為圖案，為員工，、、分別表示紅、黃、藍三種顏色.

下面證明：當時，必存在兩個人滿足要求.

事實上，把所有人的文化衫的顏色和圖案如上制成表格，若存在兩個人的某兩種圖案的4件文化衫的顏色全部相同，則必存在一個矩形子表，這個子表四個角的方格中的字母（顏色）相同.

若對于某個顏色（以紅色為例），設(shè)分到件紅色文化衫.則當時（約定當時，），必存在四個角都是的矩形.這是因為，考慮每一列兩個構(gòu)成的“對子”，一共只有如表2所示的6種.當時，必有兩列會出現(xiàn)相同的對子，從而，必有四個角都是的矩形.

表2

當時，任取其中19個人，他們的所有文化衫的顏色中，至少有一種顏色出現(xiàn)了不少于（次），不妨設(shè)為紅色.

設(shè)其中分到（為非負整數(shù)）件紅色文化衫.則.

由調(diào)整法易知，當取最小值時，對任意，有.

注意到，則在中有19個1和7個2時，取得最小值.

這表明，當時，必存在四個角都是同一個字母的矩形子表.

綜上，所求的最小值為19.