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）设G中分成的83个子集的元素个数分别为ni（1≤i≤83），1=1994，则m（G）=．可证只有当各ni的值相差不超过1时，m（G）才能取得最小值，从而可得当81组中有24个点，2组中有25个点时，m（G）达到最小值；
（2）取5个点为一小组，按图1染成a、b二色；如图2，每个小圆表示一个五点小组．同组间染色如图1，不同组的点间的连线按图2染成c、d两色，由此可得结论．
【解析】
（1）设G中分成的83个子集的元素个数分别为ni（1≤i≤83），1=1994．且3≤n1≤n2≤…≤n83．
则m（G）=．即求此式的最小值．
设nk+1＞nk+1，即nk+1-1≥nk+1，则+-（+）=-＜0．
这就是说，当nk+1与nk的差大于1时，
可用nk+1-1及nk+1代替nk+1及nk，而其余的数不变．此时，m（G）的值变小．
于是可知，只有当各ni的值相差不超过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的点为顶点的三边颜色相同的三角形．