Question

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

Answer 1

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