Question

給定平面上的點集P={P₁，P₂，…，P₁₉₉₄}，P中任三點均不共線，將P中的所有的點任意分成83組，使得每組至少有3個點，且每點恰好屬于一組，然后將在同一組的任兩點用一條線段相連，不在同一組的兩點不連線段，這樣得到一個圖案G，不同的分組方式得到不同的圖案，將圖案G中所含的以P中的點為頂點的三角形個數記為m（G）．
（1）求m（G）的最小值m．
（2）設G*是使m（G*）=m的一個圖案，若G*中的線段（指以P的點為端點的線段）用4種顏色染色，每條線段恰好染一種顏色．證明存在一個染色方案，使G*染色后不含以P的點為頂點的三邊顏色相同的三角形．

Answer 1

【答案】分析：（1）設G中分成的83個子集的元素個數分別為n_i（1≤i≤83），₁=1994，則m（G）=．可證只有當各n_i的值相差不超過1時，m（G）才能取得最小值，從而可得當81組中有24個點，2組中有25個點時，m（G）達到最小值；
（2）取5個點為一小組，按圖1染成a、b二色；如圖2，每個小圓表示一個五點小組．同組間染色如圖1，不同組的點間的連線按圖2染成c、d兩色，由此可得結論．
解答：解：（1）設G中分成的83個子集的元素個數分別為n_i（1≤i≤83），₁=1994．且3≤n₁≤n₂≤…≤n₈₃．
則m（G）=．即求此式的最小值．
設n_k+1＞n_k+1，即n_k+1-1≥n_k+1，則+-（+）=-＜0．
這就是說，當n_k+1與n_k的差大于1時，
可用n_k+1-1及n_k+1代替n_k+1及n_k，而其余的數不變．此時，m（G）的值變小．
于是可知，只有當各n_i的值相差不超過1時，m（G）才能取得最小值．
∵1994=83×24+2，∴當81組中有24個點，2組中有25個點時，m（G）達到最小值．
∴m=81+2=81×2024+2×2300=168544．
（2）取5個點為一小組，按圖1染成a、b二色，共五個小組；如圖2，每個小圓表示一個五點小組．
同組間染色如圖1，不同組的點間的連線按圖2染成c、d兩色．
這25個點為一組，共得83組，染色法相同．
其中81組去掉1個點及與此點相連的所有線，即得一種滿足要求的染色
即存在一個染色方案，使G*染色后不含以P的點為頂點的三邊顏色相同的三角形．
點評：本題考查組合知識，考查學生分析解決問題的能力，難度大．