Question

【題目】有2013位來(lái)自不同國(guó)家的代表參加一個(gè)會(huì)議，每位代表都懂得若干種語(yǔ)言，已知其中任意四位代表之間都可進(jìn)行交談而不需要此四位代表以外的其他人幫助，即此四人中的任意兩人都能講同一種語(yǔ)言而實(shí)現(xiàn)直接溝通，或者通過(guò)第三個(gè)人的翻譯實(shí)現(xiàn)間接溝通，或者通過(guò)他們各自的翻譯能講的同一種語(yǔ)言實(shí)現(xiàn)低效的間接溝通，證明：可以將所有代表分配住進(jìn)671個(gè)房間，每個(gè)房間住3人，使得每個(gè)房間的3人都可以交談。

Answer 1

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

【解析】

首先證明兩個(gè)引理.

引理1 4階連通圖中有三點(diǎn)組成連通子圖.

引理1的證明：由的連通性知其存在生成樹(shù)，將該樹(shù)去掉一個(gè)懸掛點(diǎn)，得到三點(diǎn)連通子圖.

引理2 若6階圖的任意四階子圖都連通，則可以按頂點(diǎn)劃分為兩個(gè)連通的三階子圖.

引理2的證明：顯然，為連通圖.

考慮的生成樹(shù).

（1）若至少有4個(gè)懸掛點(diǎn)、、、，由引理1知其中存在三點(diǎn)組成連通子圖，生成樹(shù)去掉這三點(diǎn)后仍連通，故結(jié)論成立.

（2）若的懸掛點(diǎn)不多于個(gè)，只有如圖的兩種情形，均使結(jié)論成立.

回到原題：

由引理1，選出四個(gè)人，其中必有三人可交流，安排同一房間，另一人回到人群；經(jīng)過(guò)次選四人組，可在669個(gè)房間中各安排三人可交流；剩下六人由引理2可分住兩個(gè)房間，每個(gè)房間各三人可交流.