Question

【題目】有2012位學(xué)者參加某數(shù)學(xué)會議，他們中有些人相互認(rèn)識，且滿足：

（1）每個人至少認(rèn)識其中的671個人；

（2）對于其中任意兩個人、，若、相互不認(rèn)識，則總可以通過其他人間接認(rèn)識，即存在，使得認(rèn)識，認(rèn)識，認(rèn)識；

（3）不可以將2012位學(xué)者排成一排，使得相鄰的兩個人相互認(rèn)識.

證明：可以將2012位學(xué)者分成兩組，其中一組能夠排成一圈，使得相鄰的人相互認(rèn)識，另一組任何兩個人不認(rèn)識.

Answer 1

【答案】見解析

【解析】

將2012位學(xué)者看作2012個點，與相鄰當(dāng)且僅當(dāng)與相互認(rèn)識，這樣就得到了一個圖.

取最長的一條鏈，不妨設(shè).

由條件（3）知.

設(shè)表示與相鄰的點的集合.則、.

，，，.

由鏈的最長性，知對任意的，.

下面用反證法證明：.

假設(shè).則，矛盾.

故.

設(shè).則構(gòu)成一個圈.

對于余下的點：與不相連.除以外的任意兩點、，若與相連，則一定存在一條包含了、和的一條鏈，這樣就找到了比更長的鏈，矛盾.故與不相連.

綜上，可以將2012位學(xué)者分成兩組，其中一組能夠排成一圈，使得相鄰的人相互認(rèn)識，另一組任何兩人人不認(rèn)識.