Question

10個學生參加n個課外小組，每一個小組至多5個人，每兩個學生至少參加某一個小組，任意兩個課外小組，至少可以找到兩個學生，他們都不在這兩個課外小組中．求n的最小值．

Answer 1

解：設(shè)10個學生為，，…，，n個課外小組，，…，．

首先，每個學生至少參加兩個課外小組．否則，若有一個學生只參加一個課外小組，設(shè)這個學生為，由于每兩個學生至少在某一個小組內(nèi)出現(xiàn)過，所以其它9個學生都與他在同一組出現(xiàn)，于是這一組就有10個人了，矛盾．    

若有一學生恰好參加兩個課外小組，不妨設(shè)恰好參加，，由題設(shè)，對于這兩組，至少有兩個學生，他們沒有參加這兩組，于是他們與沒有同過組，矛盾．

所以，每一個學生至少參加三個課外小組．于是n個課外小組，，…，的人數(shù)之和不小于3×10=30．

另一方面，每一課外小組的人數(shù)不超過5，所以n個課外小組，，…，的人數(shù)不超過5n，  故  5n≥30，   所以n≥6．       

下面構(gòu)造一個例子說明n=6是可以的．

，，，

，，．

容易驗證，這樣的6個課外小組滿足題設(shè)條件．

所以，n的最小值為6．