Question

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

Answer 1

【答案】

【解析】

先證明引理.

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

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

引理的證明：設是各項頂點中度最大的頂點，設與相鄰的點的集合為，

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

于是，

，

又，所以，.

下面證明原題.

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

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

故，

另一方面，.

所以， ， ①

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

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

綜上所述，.

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

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

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