Question

【題目】平面上有n個點，任意三點不共線，任意兩點之間連一條線段，并將每條線段染為紅色與藍色之一，稱三邊顏色相同的三角形為“同色三角形”．記同色三角形的個數為S．

（1）若，對于所有可能的染法，求S的最小值；

（2）若（整數），對于所有可能的染法，求S的最小值．

Answer 1

【答案】

【解析】

對于（），統一證明：S的最小值為．

因為共有個三角形，所以，非同色三角形有個．

稱兩條鄰邊（有一個公共點）同色的角為同色角．

接下來計算同色角的個數．

一方面，同色角的個數為

．

另一方面，對于每個點A，由點A引出的條邊中，若一種顏色的邊有i條，則另一種顏色的邊有（）條．

于是，以A為頂點的同色角的個數為，

其中，當，1時，．

設．

從而，當時，嚴格單調下降．

則以A為頂點的同色角的個數至少為．

故．

下面的例子說明為S的最小值．

設這2k個點分別為．

將兩兩之間的連線染為紅色，兩兩之間的連線染為紅色．對于所有i、，將、之間的連線染為藍色，則不存在藍色三角形，且以中任意三個點為頂點的三角形均為紅色三角形，以中任意三個點為頂點的三角形均為紅色三角形．

因此，同色三角形的個數為