【数学】2020届一轮复习人教B版组合与构造作业

【数学】2020届一轮复习人教B版组合与构造作业

‎16组合与构造2016-2018年历年数学联赛 ‎2017A三、（本题满分50分）将方格纸中每个小方格染三种颜色之一，使得每种颜色的小方格的个数相等。若相邻两个小方格的颜色不同，则称他们的公共边为“分割边”。试求分割边条数的最小值。‎ ‎★解析：记分割边的条数为.首先，将方格纸按如图所示分成三 个区域，分别染成三种颜色，粗线上均为分割边，此时共有56条 分割边，即。‎ 下面证明.‎ 将方格纸的行从上至下依次记为,,,列从左至右依次记为 ‎,,,行中方格出现的颜色数记为，‎ 列中方格出现的颜色数记为，三种颜色分别记为，，，‎ 对于一种颜色，设是表示含有色方格的函数与列数之和.‎ 记，同理定义，‎ 则①‎ 由于染色的方格有个，设含有色方格的行有个，列有个，则色方格一定在这行和列的交叉方格中，因此.从而 即.②‎ 由于在行中有种颜色的方格，因此至少有条分割边，同理在行中有种颜色的方格，因此至少有条分割边，于是，‎ ‎③‎ 下面分两种情形讨论.‎ ‎⑴当有一行或有一列全部方格同色时，不妨设有一行全为色，从而方格纸的33列中均含有的方格，由于的方格有363个，故至少有行中含有色方格。于是。④‎ 由①③④得 ‎⑵没有一行或没有一列全部方格同色时，则对任意，均有，，从而由②知，‎ 综上可知，分割边条数的最小值为。‎ ‎2017A四、（本题满分50分）。设均是大于的整数，，是个不超过的互不相同的正整数，且互素。证明：对任意实数，均存在一个（），使得，这里表示实数到它最近的整数的距离。‎ ‎★证明：首先证明两个引理：‎ 引理1：存在整数，满足，并且，.‎ 由于互素，即，有裴蜀定理，存在整数，满足。①‎ 下面证明，通过调整，存在一组满足①，且，记，‎ ‎。‎ 如果，那么存在，于是，又是大于1的整数，故由①可知，存在，令，，（，），则 ‎，② 并且，，‎ 所以，‎ 如果，则存在，因此有一个.令，，（，），那么②成立，并且，与上面类似可以证明到：‎ ‎，，即说明与均是非负整数，故通过有限次上述的调整，可以得到一组使得①成立，并且结论获证。‎ 引理2：①对任意的实数，均有；②对任意整数和实数，有；‎ 由于对任意整数和实数，均有，于是不妨设，此时，，若，不妨设，则，从而 若，不妨设同号，则当时，有，‎ 此时；当时，注意到总有，故 ‎；故①得证；‎ 又，由①知，②是成立的。‎ 接下来回到原题，由结论①存在整数，满足，并且，.于是，，由引理2得，‎ 因此，③‎ 若，则由③知，‎ 若，则在中存在两个相邻的正整数。不妨设相邻，则，故与中有一个不小于。‎ 综上，总存在存在一个（），使得 ‎2016A三、（本题满分50分）给定空间个点，其中任意四点不在一个平面上。将某些点之间用线段相连，若得到的图形中没有三角形也没有空间四边形，试确定所连线段数目的最大值。‎ ‎★解析：以这10个点为顶点，所连线段为边，得到一个10阶简单图G，我们证明G的变数不超过15.‎ 设G的顶点为，一共有条边，用表示顶点的度。若对都成立，则。‎ 假设存在满足，不妨设，且与均相邻.于是之间没有边，否则就成三角形，所以与之间恰有条边.‎ 对每个（），至多与中的一个顶点相邻（否则设与，（）相邻，则，，，就对应了一个空间四边形的四个顶点，这与题意矛盾），从而与之间的边数至多条。‎ 在这个顶点之间，由于没有三角形，由托兰定理，至多条边，因此G的边数 例如如图所示的就有条边，且满足要求。‎ 综上所述，所连线段数目的最大值为。‎