组合结构计算题(组合结构的计算次序)

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

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

6、可以构造：休息前为1，2，3，…，2n+1，休息后为1，3，5，…，2n+1，2，4，6，…，2n。

7、n min=10。

当n=9时，我们要构造一个二色K9，使图中任何2个颜色相同的同色三角形都至少有一个公共点，为了容易计算同色三角形的个数，考察极端情形——令某种颜色的边尽可能多。注意到2个没有公共点的三角形至少有6个不同顶点，从而K5中任何两个三角形都有公共点，于是，可构造一个红色的K5（其中没有2个无公共点的同色三角形）：A1A2A3A4A5，另外，将边A6A7、A6A8、A6A9染红色，而其余的边都染蓝色，则其中红色三角形只能在红色的K5中，任何2个都有公共点。此外，如果图中去掉蓝边A7A8、A8A9、A9A7及所有红边，则得到一个蓝色的2部分图K3，5，其中没有三角形，从而所有蓝色三角形都含有△A7A8A9中的一条边，于是，任何两个蓝色三角形都含有△A7A8A9中的2条边，这2条边有公共点，即任何两个蓝色三角形都有公共点，从而没有2个没有公共点的颜色相同的同色三角形。当n<9时，在上述染色后的K9中去掉9–n个点及其关联的边，得到的图不含两个颜色相同的无公共顶点的同色三角形。

另一方面，若n≥10，则将Kn二染色，必有两个颜色相同的无公共顶点的同色三角形。反设结论不成立，考察其中的一个K10。用实线表示红色，用虚线表示蓝色。先证明K10中必有一个红色三角形和一个蓝色三角形，它们恰有一个公共点。

实际上，二色K10中必有同色三角形，不妨设为红色△ABC。去掉点A、B、C，剩下的K7中又必有同色△DPQ，显然△DPQ为蓝色。考察△ABC与△DPQ之间的9条边，其中必有5条边同色，设为蓝色。将此5条蓝色边归入顶点A、B、C，必有某个点，设为C，引出两条蓝色边，设此两条蓝色边为CP、CQ，这样，红色△ABC与蓝色△CPQ恰有一个公共顶点C。

在K10中去掉点A、B、C、P、Q，剩下的K5中没有同色三角形（否则，其同色三角形与△ABC、△CPQ无公共点），必是一个红色的C5：DEFGH 和一个蓝色的C5：DFHEG（五角星）。

因为点C与K5：DEFGH组成的K6中有同色三角形，由对称性，不妨设有红色△CDH。考察点B与K5：DEFGH组成的K6，其中有2个同色三角形△1、△2，但K5：DEFGH中没有同色三角形，所以△1、△2都有一个顶点为B。显然△1、△2都是红色（因为其与△CPQ无公共点），从而△1、△2都至少有一个顶点为H、D之一。如果△1、△2都不同时以D、H为顶点，则△1、△2只能分别为△BHG、△BDE，所以BH、BD为红边。如果△1、△2中有一个同时以D、H为顶点，也有BH、BD为红边。所以，不论哪种情况，都有BH、BD为红边。同理，AH、AD为红边（图1-10）。

图1-10

这样，BE为蓝边（否则有红色△ACH、△BDE），BG为蓝边（否则有红色△ACD、△BGH）。此时，有蓝色△BEG、△CPQ，矛盾。

8、rmax=2。

首先，构造两个没有公共顶点的红色K5，两个红色K5之间的边都染蓝色，得到一个二色的10阶完全图G。对G中任何3个顶点，必有两个点在同一个K5中，从而连接这两点的边为红色，所以G中没有蓝色三角形。

又G中的红色三角形必定属于某个K5中。如果r≥3，考察G中3个红色三角形，必有2个红色三角形在同一个K5中，但K5只有5个顶点，从而这两个三角形有公共点，矛盾。所以r≤2。

其次，由上题，2色K10中必有2个相同颜色的同色三角形，且两个三角形没有公共顶点，故rmax=2。

9、rmax=2。

首先，将K14中一个K8：A1A2…A8和一个K3，3：A9A10A11-A12A13A14的边染红色，其中K8与K3，3没有公共顶点，将K14中的其他边都染蓝色，得到一个2色的14阶完全图G。

因为红色K3，3中没有红色三角形，所以红色三角形都在红色的K8中，但3个两两没有公共顶点的红色三角形有9个不同顶点，而K8只有8个顶点，所以不存在3个两两没有公共顶点的红色三角形。

去掉2个蓝色△A9A10A11、△A12A13A14的边，剩下的蓝色边构成一个蓝色的K6，8，其中无蓝色三角形，于是，G中每个蓝色三角形都至少含有△A9A10A11、△A12A13A14中的一条边。考察G中任何3个蓝色三角形，它们一共至少含有△A9A10A11、△A12A13A14中的3条边，这3条边中一定有2条同时属于△A9A10A11、△A12A13A14中的某一个，从而这2条边有公共点，所以不存在3个两两没有公共顶点的蓝色三角形。

所以r≤2。

下面证明，对任何2色K14，其中必有2个相同颜色的同色三角形，它们没有公共顶点。

实际上，任何2色K6中必有同色三角形，在K14中取一个同色△ABC，去掉点A、B、C，剩下的K11中又有同色△DEF。再去掉点D、E、F，剩下的K8中又有同色△GHI，这3个同色三角形中必有2个颜色相同，且它们没有公共点。

故rmax=2。

10、rmax=t-1。

首先，当t为奇数时，令t=2s-1，则3t+1=6s-2。构造两个没有公共顶点的红色K3s-1，两个红色K3s-1之间的边都染蓝色，得到一个2色的3t+1阶完全图G。对G中任何3个顶点，必有两个点在同一个K3s-1中，从而连接这两点的边为红色，所以G中没有蓝色三角形。

又G中的红色三角形必定属于某个K3s-1中。如果r≥t=2s-1，考察G中2s-1个红色三角形，必有s个红色三角形在同一个K3s-1中，但K3s-1只有3s-1个顶点，从而必有两个三角形有公共点，矛盾。所以r≤t-1。

当t为偶数时，令t=2s，则3t+1=6s+1。构造一个红色K3s-1和一个红色K3s+2，使K3s-1与K3s+2没有公共顶点，将K3s-1与K3s+2之间的边都染蓝色，得到一个2色的3t+1阶完全图G。对G中任何3个顶点，必有两个点在红色K3s-1或K3s+2中，从而连接这两点的边为红色，所以G中没有蓝色三角形，即G中的同色三角形都为红色。

又G中的红色三角形必定属于K3s-1或K3s+2中。如果r≥t=2s，考察G中2s个红色三角形，必有s个红色三角形在红色K3s-1中，但K3s-1只有3s-1个顶点，从而必有两个三角形有公共点，矛盾。或者有s+1个红色三角形在红色K3s+2中，但K3s+2只有3s+2个顶点，从而这s+1个三角形中必有两个有公共点，矛盾。所以r≤t。

其次，用归纳法证明：以任何方式将k3t+1的边2–染色时，总存在t-1个同色三角形，其中任何两个三角形没有公共顶点。

当t=2时，结论显然成立。设t=k时结论成立。当t=k+1时，取其中一个同色△ABC，去掉点A、B、C，剩下的图由归纳假设有k-1个同色三角形，其中任何两个三角形没有公共顶点。连同△ABC，共有k个两两没有公共点的同色三角形。

故rmax=t-1。

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