Question

【題目】個(gè)人在某個(gè)節(jié)日期間互通電話問候，已知其中每個(gè)人至多打通了三個(gè)朋友家的電話，任何兩個(gè)人之間至多進(jìn)行一次通話，且任何三個(gè)人中至少有兩人，其中一個(gè)人打通了另一個(gè)人家里的電話，求的最大值.

Answer 1

【答案】

【解析】

先證明引理.

引理 階簡單圖中不存在，則.

其中，表示的邊數(shù).

引理的證明：設(shè)是各項(xiàng)頂點(diǎn)中度最大的頂點(diǎn)，設(shè)與相鄰的點(diǎn)的集合為，

與不相鄰的點(diǎn)的集合為 ，由于中無三角形，從而，在中沒有邊，則的其他邊都在中或之間，這樣的邊都是由頂點(diǎn)引出的.

于是，

，

又，所以，.

下面證明原題.

用個(gè)點(diǎn)表示個(gè)人，如果一個(gè)人打通了另一個(gè)人家里的電話，則連一條從到的有向邊，得到一個(gè)簡單的有向圖.

一方面，中無三角形，由引理有，

故，

另一方面，.

所以， ， ①

當(dāng)為奇數(shù)時(shí)，式①變?yōu)?/span>，解得；

當(dāng)為偶數(shù)時(shí)，式①變?yōu)?/span>，解得.

綜上所述，.

最后，是可能的，構(gòu)造兩個(gè),對其中每個(gè)七邊形，令指向，則構(gòu)圖合乎條件，

首先，每個(gè)點(diǎn)作為始點(diǎn)都恰引出3條有向邊，從而，每個(gè)人至多打通了3個(gè)朋友家的電話.

其次，對任何三個(gè)點(diǎn)，由抽屜原理知，必有兩個(gè)點(diǎn)，在同一個(gè)中，若，則打通了家中的電話，若則打通了家中的電話.