题目内容

【题目】给定平面上的点集,中任三点均不共线。将中所有的点任意分成83组,使得每组至少有3个点,且每点恰好属于一组,然后将在同一组的任两点用一条线段相连,不在同一组的两点不连线段,这样得到一个图案。不同的分组方式得到不同的图案。将图案中所含的以中的点为顶点的三角形的个数记为。

(1)求的最小值;

(2)设是使的一个图案,若将中的线段(指以的点为端点的线段)用4种颜色染色,每条线段恰好染一种颜色。证明存在一个染色方案,使染色后不含以的点为顶点的三边颜色相同的三角形。

【答案】(1)168544;(2)见解析

【解析】

显然,每个图案由的点的分组方法唯一确定.

(1)设,由分组,,…,得到,其中为第组的点构成的集合,,2,…,83.

令,则有,且.

下证当时,有.

事实上,若存在,使得,不妨设,则作的点的分组,,…,(为第组的点构成的集合,),使得

这样的分组显然存在.于是,对于由分组,,…,得到的图案,有

.

而

.

∵.

∴.

∴.这与的最小性相矛盾.

∵,

∴.

(2)设图案由分组,,…,得到,这里表示第组的点构成的集合.由(1)不妨设,.下面给出的一个染色方法,使得用四种不同颜色染后不含三边颜色相同的三角形.

我们将集合及所连线段构成的图形称为的第块,记为,,2,…,83.对于,令,使得,.将每个子集中任两点所连线段用图(1)所示的方法去染,将不同子集与之间所连线段用途(2)所示的方法去染,图中,,,分别代表四种不同的颜色,这样染后的显然不含三边颜色相同的三角形.

对于,可用染的方法去染,至于的染法,可先加一点并将该点与原来的24点各连一条线段,染后按的染法染好后,再把加的一点及与该点所连的线段去掉,这样染后的也不含三边颜色相同的三角形.

综上可知,结论成立.

练习册系列答案
相关题目

违法和不良信息举报电话:027-86699610 举报邮箱:58377363@163.com

精英家教网