Question

【题目】有2008名学生参加大型公益活动．若有两名学生互相认识，则将这两名学生看作一个合作小组．

（1）求合作小组数目的最小值，使得无论学生认识的情况如何，都存在三名学生，他们两两都在一个合作小组；

（2）若合作小组数目为，证明：存在四名学生、、、，使得和、和、和、和分别为一个合作小组．

Answer 1

【答案】(1) (2)见解析

【解析】

（1）设．

下面证明：．

将学生分为两大组，每大组中有名学生，且每大组中的学生互相不认识，而每个学生都和另外一个大组中的每个学生认识，则可以组成个合作小组，但是不存在三名学生，他们两两都在一个合作小组．

若有个合作小组，设学生认识的学生最多，且认识个学生，分别设为，，…，．

若存在、满足与互相认识，则、、满足条件；

若，，…，中任意两名学生都不在一个合作小组，则合作小组的数目不超过．矛盾．

因此，．

（2）设，，名学生分别为，，…，，他们认识学生的数目分别为，，…，，则．

考虑每个学生认识的学生中所有可能的两个小组，其总数为

．

所以，存在一个两人小组和，他们都认识和．