Question

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

Answer 1

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