1981年~2019年全国高中数学联赛试题分类汇编：15 组合与构造 Word版含答案.doc

PAGE 1981年~2019年全国高中数学联赛试题分类汇编 组合与构造部分 2019A四、（本题满分 50 分） 设V 是空间中 2019 个点构成的集合，其中任意四点不共面．某些点之间连有线段，记 E 为这些线段构成的集合．试求最小的正整数n，满足条件：若 E 至少有n个元素，则 E 一定含有 908 个二元子集，其中每个二元子集中的两条线段有公共端点，且任意两个二元子集的交为空集． ★解析：为了叙述方便，称一个图中的两条相邻的边构成一个“角”． 先证明一个引理：设是一个简单图，且是连通的，则含有个两两无公共边的角（这里表示实数的整数部分）． 引理的证明：对的元素个数归纳证明．当时，结论显然成立．下面假设，并且结论在较小时均成立．只需证明，在中可以选取两条边构成一个角，在中删去这两条边后，剩下的图含有一个连通分支包含条边．对这个连通分支应用归纳假设即得结论成立． 考虑中的最长路，其中是互不相同的顶点．因为连通，故. 情形1：,由于是最长路，的邻点均在中，设，其中．则是一个角，在中删去这两条边．若处还有第三条边，则剩下的图是连通的；若处仅有被删去的两条边，则成为孤立点，其余顶点仍互相连通．总之在剩下的图中有一个连通分支含有条边． 情形 2：， ．则 是一个角，在中删去这两条边后，都成为孤立点，其余的点互相连通，因此有一个连通分支含有条边． 情形 3：，，且与中某个点相邻．则是一个角，在中删去这两条边后，成为孤立点，其余点互相连通，因此有一个连通分支含有 条边． 情形 4：，，且与某个相邻．由于是最长路，故的邻点均在之中．因是一个角，在中删去这两条边，则是孤立点．若处仅有边，则删去所述边后也是孤立点，而其余点互相连通．若处还有其他边，，则删去所述边后，除外其余点互相连通．总之，剩下的图中有一个连通分支含有. 引理获证．………………20 分 回到原题，题中的和可看作一个图． 首先证明． 设．在中，首先两两连边，再删去其中条边（例如），共连了条边，则这个点构成的图是连通图．再将剩余的个点配成对，每对两点之间连一条边，则图中一共连了条线段．由上述构造可见，G 中的任何一个角必须使用相连的边，因此至多有个两两无公共边的角．故满足要求的不小于．……30 分 另一方面，若，可任意删去若干条边，只考虑的情形． 设有个连通分支，分别有个点，及条边．下面证明中至多有个奇数． 反证法，假设中有至少个奇数，由于是奇数， 故中至少有 981 个奇数，故．不妨设 都是奇数，显然． 令，则有（），， 故，利用组合数的凸性，即对，有。 可知当由个以及一个构成时，取得最大值．于是 ，这与①矛盾．从而中至多有 979 个奇数． ……40 分 对每个连通分支应用引理，可知中含有个两两无公共边的角，其中。 综上，所求最小的是． ……50 分 2019B四、（本题满分50分） 将一个凸边形的每条边任意染为红、黄、蓝三种颜色之一，每种颜色的边各条．证明：可作这个凸边形的条在内部互不相交的对角线将其剖分成个三角形，并将所作的每条对角线也染为红、黄、蓝三种颜色之一，使得每个三角形的三条边或者颜色全部相同，或者颜色互不相同． ★证明：我们对归纳证明加强的命题：如果将凸边形的边染为三种颜色，并且三种颜色的边均至少有一条，那么可作满足要求的三角形剖分．…………10 分 当时，若三种颜色的边数为,由对称性，只需考虑如下两种情形， 分别可作图中所示的三角形剖分． 若三种颜色的边数为,由对称性，只需考虑如下三种情形，分别可 作图中所示的三角形剖分． ……20 分 假设结论对（）成立，考虑的情形，将凸边形记为． 情形 1：有两种颜色的边各只有一条．不妨设色边各只有一条．由于，故存在连续两条边均为色，不妨设是．作对角线，并将 染为 色，则三角形的三边全部同色．此时凸边形的三种颜色的边均至少有一条，由归纳假设，可对其作符合要求的三角形剖分．………………30分 情形 2：某种颜色的边只有一条，其余颜色的边均至少两条．不妨设色边只有一条，于是可以选择两条相邻边均不是色，不妨设均不是色，作对角线，则有唯一的染色方式，使得三角形的三边全部同色或互不同色．此时凸边形的三种颜色的边均至少有一条，由归纳假设，可对其作符合要求的三角形剖分． ………………40 分 情形 3：每种颜色的边均至少两条．作对角线，则 有唯一的染色方式，使得三角形的三边全部同色或互不同色．此时凸边形 的三种颜色的边均至少有一条，由归纳假设，可对其作符合要求的三角形剖分． 综合以上种情形，可知的情形下结论也成立． 由数学归纳法，结论获证． ………………50 分 2017A三、（本题满分50分）将方格纸中每个小方格染三种颜色之一，使得每种颜色的小方格的个数相等。若相邻两个小方格的颜色不同，则称他们的公共边为“分割边