题目内容
给定平面上的点集P={P1，P2，…，P1994}，P中任三点均不共线，将P中的所有的点任意分成83组，使得每组至少有3个点，且每点恰好属于一组，然后将在同一组的任两点用一条线段相连，不在同一组的两点不连线段，这样得到一个图案G，不同的分组方式得到不同的图案，将图案G中所含的以P中的点为顶点的三角形个数记为m（G）．（1）求m（G）的最小值m．
（2）设G*是使m（G*）=m的一个图案，若G*中的线段（指以P的点为端点的线段）用4种颜色染色，每条线段恰好染一种颜色．证明存在一个染色方案，使G*染色后不含以P的点为顶点的三边颜色相同的三角形．
【答案】分析：（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的点为顶点的三边颜色相同的三角形．
点评：本题考查组合知识，考查学生分析解决问题的能力，难度大．
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的点为顶点的三边颜色相同的三角形．
点评：本题考查组合知识，考查学生分析解决问题的能力，难度大．
练习册系列答案
怎样学好牛津英语系列答案
相关题目
x2，实数p，q满足p2-4q≥0，x1，x2是方程x2-px+q=0的两根，记φ（p，q）=max{|x1|，|x2|}.
p0）（p0≠0）作L的切线教y轴于点B。证明：对线段AB上任一点Q（p，q）有φ（p，q）=
；
p12），E′（p2，
|P1|＞|P2|
；
（x+1）2-
}，当点（p，q）取遍D时，求φ（p，q）的最小值 （记为φmin）和最大值（记为φmax）。
．实数p，q满足
，x1，x2是方程
的两根，记
。
作L的切线教y轴于点 B．证明：对线段AB上任一点Q（p，q）有
，切点分别为
，
X
;
（x+1）2-
}．当点（p,q）取遍D时，求
的最小值 （记为
）和最大值（记为
）．