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），

83

i=1

n₁=1994，则m（G）=

83

i=1

C

3 n

．可证只有当各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），

83

i=1

n₁=1994．且3≤n₁≤n₂≤…≤n₈₃．
则m（G）=

83

i=1

C

3 n

．即求此式的最小值．
设n_k+1＞n_k+1，即n_k+1-1≥n_k+1，则

C

3 ni+1

+

C

3 ni-1

-（

C

3 ni

+

C

3 ni+1

）=

C

2 ni

-

C

2 ni+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

C

3 24

+2

C

3 25

=81×2024+2×2300=168544．
（2）取5个点为一小组，按图1染成a、b二色，共五个小组；如图2，每个小圆表示一个五点小组．
同组间染色如图1，不同组的点间的连线按图2染成c、d两色．
这25个点为一组，共得83组，染色法相同．
其中81组去掉1个点及与此点相连的所有线，即得一种满足要求的染色
即存在一个染色方案，使G*染色后不含以P的点为顶点的三边颜色相同的三角形．

点评：本题考查组合知识，考查学生分析解决问题的能力，难度大．