Question

【題目】有2008名學(xué)生參加大型公益活動(dòng)．若有兩名學(xué)生互相認(rèn)識(shí)，則將這兩名學(xué)生看作一個(gè)合作小組．

（1）求合作小組數(shù)目的最小值，使得無(wú)論學(xué)生認(rèn)識(shí)的情況如何，都存在三名學(xué)生，他們兩兩都在一個(gè)合作小組；

（2）若合作小組數(shù)目為，證明：存在四名學(xué)生、、、，使得和、和、和、和分別為一個(gè)合作小組．

Answer 1

【答案】(1) (2)見(jiàn)解析

【解析】

（1）設(shè)．

下面證明：．

將學(xué)生分為兩大組，每大組中有名學(xué)生，且每大組中的學(xué)生互相不認(rèn)識(shí)，而每個(gè)學(xué)生都和另外一個(gè)大組中的每個(gè)學(xué)生認(rèn)識(shí)，則可以組成個(gè)合作小組，但是不存在三名學(xué)生，他們兩兩都在一個(gè)合作小組．

若有個(gè)合作小組，設(shè)學(xué)生認(rèn)識(shí)的學(xué)生最多，且認(rèn)識(shí)個(gè)學(xué)生，分別設(shè)為，，…，．

若存在、滿足與互相認(rèn)識(shí)，則、、滿足條件；

若，，…，中任意兩名學(xué)生都不在一個(gè)合作小組，則合作小組的數(shù)目不超過(guò)．矛盾．

因此，．

（2）設(shè)，，名學(xué)生分別為，，…，，他們認(rèn)識(shí)學(xué)生的數(shù)目分別為，，…，，則．

考慮每個(gè)學(xué)生認(rèn)識(shí)的學(xué)生中所有可能的兩個(gè)小組，其總數(shù)為

．

所以，存在一個(gè)兩人小組和，他們都認(rèn)識(shí)和．