组合结构计算题(组合构型)

导语：组合构造第1章：容易求值6

【附】为便于有需要者编辑修改，特提供纯文本文档如下：

例10、求最小的正整数n，使以任何方式将kn的边2-染色时，总存在两个没有公共边的颜色相同的同色三角形（1991年中国国家集训队考试题）。

分析与解：为了找到“两个没有公共边的颜色相同的同色三角形”，一个充分条件是先找3个同色三角形，两两无公共边，则由抽屉原理，必有2个同色三角形颜色相同。而此结论成立的一个充分条件是n=9：先找一个同色三角形，去掉此同色三角形的2个顶点，剩下的图中有K 7 ，又有2个同色三角形。

现在的问题是，n能否更小？经实验，找不到n=8的反例，而n=7的反例存在。于是猜想n可以为8。

当n=7时，从易于计算同色三角形的个数的角度考虑，在图中将某种颜色尽可能多地染边。

注意到2个没有公共边的三角形至少有5个不同顶点，从而K4中任何两个三角形都有公共边，于是，可构造一个红色的K4（其中没有2个无公共边的同色三角形）：A1A2A3A4，另外取一个长为3的红色链：A5A6A7，其余的边都染蓝色，则其中红色三角形只能在红色的K 4中，都有公共边（图1-8）。此外，如果在图中去掉蓝边A5A7及所有红边，则得到一个蓝色的2部分图，其中没有三角形，从而所有蓝色三角形都含有边A5A7。即所有蓝色三角形也都有公共边，从而没有2个没有公共边的颜色相同的同色三角形。

若n<7，则将上述图中去掉7-n个点及其关联的边即可。

图1-8 图1-9

另一方面，对任何二色K8，必有两个没有公共边的颜色相同的同色三角形。

反设结论不成立，用实线表示红色，用虚线表示蓝色。首先二色K8中必有同色三角形，不妨设为红色三角形A1A2A3。设想去点A1、A2及其关联的边，剩下的K6中又必有同色三角形，此三角形必为蓝色三角形，我们可假定此三角形与△A1A2A3有公共边（以便去公共点破坏三角形），从而设蓝色三角形为A3A4A5。（如果两个同色三角形没有公共点，则可进一步找到两个恰有一个公共点的同色三角形。实际上，设同色三角形为红△A1A2A3与蓝△A4A5A6，考察△A1A2A3与△A4A5A6之间的9条边，其中必有5条边同色，设为蓝色。将此5条蓝色边归入顶点A4、A5、A6，必有某个点，设为A4，引出两条蓝色边，设此两条蓝色边为A4A1，A4A2，此时，蓝色三角形A1A2A4与红色三角形A4A5A6恰有一个公共顶点A4）。

再设想二色K8中去掉点A1、A3、A5及其关联的边，在剩下的K5中不能有同色三角形，此K5必是一个红色的C5：A2A4A6A7A8和一个蓝色的C5：A2A6A8A4A7A2的并（图1-9）。

再设想二色K8中去掉A3、A5，考察A1、A2、A4、A6、A7、A8这6点的图G&39;中有两个同色三角形。这2个同色三角形△1、△2必须与△A1A2A3有公共边，否则设△1与△A1A2A3无公共边，当△1为蓝色时，△1与△A3A4A5无公共边为所求。当△1为红色时，△1与△A1A2A3无公共边为所求。于是三角形△1、△2必须以A1A2为公共边，这两个三角形只能是A1A2A4、A1A2A8。所以A1A8为红边，A1A4为红边。同样设想二色K8中去掉A1、A3，可得A5A7、A5A8为蓝色边。于是，若A3A8为红边，则三角形A1A3A8和A1A2A4为红色三角形；若A3A8为蓝边，则三角形A4A3A8和A4A5A7为蓝色三角形。矛盾。

本文内容由小媛整理编辑！