10个同学参加n个课外小组,每一个小组至多5个人,每两个学生至少参加某一个小组,任意两个课外小组,至少以找到两个学生,他们都不在这两个课外小组中.证明：n的最小值为6.

Question

10个同学参加n个课外小组,每一个小组至多5个人,每两个学生至少参加某一个小组,任意两个课外小组,至少
以找到两个学生,他们都不在这两个课外小组中.证明：n的最小值为6.

Answer 1

可设10个学生为S1,S2,S3,…,S10,n个课外小组设为G1,G2,G3,…,Gn.
由题意得,如果有一个学生只参加一个小组,例：S1只参加了G1,那么由于“每两个学生至少参加某一个小组”,所以其余9位同学都分别与S1共同参加了G1,这样一来G1就拥有了10个成员,这显然与题意相违背.
若有一位同学只参加了2个课外小组,例：S1只参加了G1,G2,基于“每两个学生至少参加某一个小组”的原则,S2---S10必然出现在G1或者G2中,这显然与“任意两个课外小组,至少可以找到两个学生,他们都不在这两个课外小组中”矛盾.
综上所述,每个学生至少参加3个课外小组,于是n个小组G1,G2,…,Gn拥有学生人数至少为3＊10＝30人,另外由于每个小组至多5个人,所以n个小组至多5n人,有5n>=30,n>=6,即n的最小值为6.