题目内容

【题目】平面上有个点,其中每两点之间的连线均染成红色或黑色.若图中总存在两个没有公共边的同色三角形,求的最小值.

【答案】8

【解析】

对于如图的七个点,并将图中的线画成红色,其余的线画成黑色.

于是图中所得到的四个三角形,其中任何两个三角形都是有公共边的红色三角形.此外对四个黑三角形也有一条公共边,因此所求的最小正整数.

下面证明时符合题目要求,用反证法.

假设对8个点每两点的连线染成红、黑两色,但不满足题目要求.

由于对于6个点,则必存在一个单色三角形,不妨设为红三角形(图中用实线连接).

这时,考察除去的其他6.,…,每两点连线染成二色的图形.由假设知,这6点存在的同色三角形只能是黑三角形,不妨设是黑三角形(图中用虚线连接).

再除去的其余5点,由假设知这5点不能有单色三角形,于是只能为如图的情形,不妨设所连线为红线,所连线为黑线.

这时,再考察由6点构成的图.由反证假设只能有两个红三角形,且这两个红三角形都以为公共边,于是这两个三角形只能是.所以为红边,为红边.类似地可证为黑边,此时若为红边则为无公共边红三角形,若为黑边,则为无公共边黑三角形,均与反证假设矛盾.

综上,所求最小正整数为.

练习册系列答案
相关题目

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

精英家教网