Question

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

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

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

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

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

Answer 1

【答案】見解析

【解析】

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

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

由條件（3）知.

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

，，，.

由鏈的最長(zhǎng)性，知對(duì)任意的，.

下面用反證法證明：.

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

故.

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

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

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