引用:
原帖由 男孩爸爸 于 2008-3-19 18:15 发表
10个学生参加n个课外小组,每一个小组至多5个人,每两个学生至少参加某一个小组,任意两个课外小组,至少可以找到两个学生,他们都不在这两个课外小组中.求n的最小值.
通过已知条件很容易知道每个同学至少属于三个不同的组,10个人两两配对共有45对,有已知条件每一对同学都至少属于一个组,而每组最多有5人,因此最多含有10对同学,这样就说明至少有5组。
接下来证明:5组是不可以的,证明过程像是绕口令,这里字母下标打字不方便,自己也可以思考一下。
最后用构造说明6组是可以的,这样n=6最小。构造如下图,10个同学分别对应1,2,。。。,10。
[
本帖最后由 wood 于 2008-3-19 22:22 编辑 ].