分组法

20O7年第2期 5 分 组 法 李 成 章 (南开大学数学科学学院，300071) (本讲适合高中) 组合，顾名思义，就是组与合．确切地说 ， 就是分组与并合．一会儿分组讨论，一会儿又 并合起来研究 ．所以，分组法是组合数学中最 基本的方法之一．仔细想来，见过与做过的许 多题目的解法中，都包含着形形色色的分组 过程，并在 证明 住所证明下载场所使用证明下载诊断证明下载住所证明下载爱问住所证明下载爱问 或求解中起着重要的作用．例 如，抽屉原理中经常用分组法来构造抽屉；又 如，换序求和中的计数、集合问题中的子集、 图论问题中的子图、方格问题中的分块等，都 明显地包含着分组处理．至于染色问题 ，每种 颜色的对象自成一组，当然是分组问题了． 本文不系统介绍上述与分组有关的各类 问题，而是集中讲述分组法在证明与论述中 起着的支配作用． 1 利用分组法计数 分组法计数是组合计数中的基本方法， 特别是在全国联赛一试中会经常遇到． 例 1 从给定的 6种不同颜色中选用若 干种颜色，给一个正方体染色，每面染一种颜 色且使每两个有公共棱的相邻面都异色．问 不同的染色 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 共有多少种(若两个已染色 的正方体中的一个经若干次翻转后的染色状 态与另一个相同，则认为二者原来的染色方 案是同一种)? (1996，全国高中数学联赛) 讲解：显然，最多用 6种颜色，最少用 3 种颜色．下面用分组法来计数． (1)使用 6种颜色时，每种颜色各染一 面．按题中约定，可经翻转使得第一种颜色朝 上。这时，下面是另 5种颜色之一，有 5种不 同的染色方法．另 4种颜色分染前后左右 4 收稿日期：20o6—11—17 个面，可从 中选定其中一种颜色染前面，于 是 ，后面是另 3种颜色之一，当然有 3种不同 的染色方法．余下的 2种颜色分染左右两面， 又有 2种不同的染色方法 ．所以，不同的染色 方法共有5 X 3 X 2=30种． (2)使用 5种颜色时，从 6种颜色中选定 5种颜色，再从 5种颜色中选定一种颜色染 相对两面，当然可以转为上下两面，共有 6× 5=3o种不同的染色方法．余下的4种颜色 分染4个侧面．选定其中一种颜色染前面，于 是，后面是另 3种颜色之一，又有 3种不同的 染色方法．余下的2种颜色分染左右两面．与 (1)中不同的是，这时，可绕着前后两面中心 的轴旋转 180~，便知只是 1种染色方法．所 以，不同的染色方法共有 90种 ． (3)使用 4种颜色时，从 6种颜色中任选 4种颜色，再从 4种颜色中选定 2种颜色各 染相对两面，不同的染色方法也是有 ： 90种． (4)使用 3种颜色时，不同的染色方法为 = 20种 ． 综上可知，所求的不 同染色方法共有 230种． 评注：此题虽然只是一道填空题，但做对 并不容易．当年的 标准 excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载 答案 八年级地理上册填图题岩土工程勘察试题省略号的作用及举例应急救援安全知识车间5s试题及答案 是 320，当然不 对．错误的原因在于(2)中最后 2种颜色分染 两面时，由于可以旋转只有 1种方法，而在标 准答案中却认为是 2种方法 ． 2 利用分组法建立不变量 分组法建立不变量是用不变量解题的常 用方法． 例2 在12X 12的超级国际象棋的棋盘 上放有一枚“超级马”，它走棋时每步从 3×4 维普资讯 http://www.cqvip.com 6 中 等 数 学 方格矩形的一角格跳到相对的角格中．问这 枚超级马能否从某一方格出发遍历每格一 次，然后回到出发点? (第 26届 IMO候选题) 讲解：(1)注意到，国际象棋棋盘上的方 格本来就是分成黑白两组的，超级马按规定 每跳一次，都是从一种颜色的方格中跳到另 一 种颜色的方格中，即每跳一步前后，超级马 所在的方格都异色(不变量)． (2)将 12X 12方格棋盘从上到下的第 1， 2，6，7，11，12这 6行方格分成一组，称为 A 组．另外 6行方格划归 组．显然，超级马从 A组方格出发跳一步，一定落人 组的某方 格之中(不变量)． (3)仅从棋盘和走棋规则来看，超级马从 组方格出发跳一步，却不一定落人 A组方 格之中．但是，如果超级马能够实现题中所要 求的走棋全过程，由于 A、 两组方格数相 同，而且从 A组方格出发又一定跳人 组方 格中，故从 组方格出发，也一定跳人 A组 方格中(不变量)．否则， 组方格先用完，超 级马就无法回到出发点了． 将(2)和(3)中两个不变量结合起来即 知，在反证假设之下，超级马每跳一步前后 ， 所在的方格都异组(不变量)．由此及(1)可 知，超级马跳动的过程既只能是 白一黑一白一黑一⋯， 黑一白一黑一白一⋯ 之一，又只能是 A A ⋯ ． A A ⋯ 之一．这导致 A、 两组方格全都分别同色， 此不可能．所以，题中所要求的行棋过程是无 法实现的． 3 利用分组法证明某种元素的存在性 例 3 设 M={1，2，⋯，20}．对于 的任 何一个9元子集 s，函数 (s)在 中取值． 求证：无论函数 怎样定义，总存在 的一 个10元子集 ，使对所有kE T，都有 ( 一{k})≠k． (1988，美国数学奥林匹克) 讲解 ：如果 10元子集 具有性质：对任 何 kE T，均有 ．厂( 一{k})≠k，则称 为“好 集”．不是好集 的 10元子集称为“坏集”．于 是，问题归结为证明：好集的存在性 ． 如果 为坏集，按定义有 k。E T，使得 ( 一{k0})=k0． 令 S=T一{k。}，则 S为 的一个 9元 子集．由于 ． 厂(S)=k。，故有 T=S U{k。}_S U{f(S)}． 这 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 明了坏集的结构，即它可由某一个 9元子集生成．其生成的办法是，对于任何一 个 9元子集 S，为它增加第 10个元素 厂(S)． 当．厂(S) S时，确实得到一个坏集．由此可 见，任何一个 9元子集至多能按上述办法生 成一个坏集．所以，坏集的总数不超过 的 所有 9元子集的个数．但 的 10元子集的 个数显然大于 的所有 9元子集的个数，因 此，好集必然存在 ． 例 4 在平面上给定两条封闭折线，每 条折线都有奇数条边且这些边所在的直线互 不相同，这其中任何三条直线都不共点．求 证 ：必可从每条折线上各取一条边，使得以二 者为一组对边可以作出一个凸四边形． (1987，全苏数学奥林匹克) 讲解：把两条折线的各一条边视为一组 称为一个“边对”．显然，每个边对中的两条边 的位置关系有三种不同情形： (1)两条边相交； (2)两条边中恰有一条边延长后与另一 条边相交(包括端点)； (3)两条边中每条边延长后都不与另一 条边相交． 将每种情形的边对视为一组，则共分为 3组．问题转化 为证 明：第三种边对 的存 在性． 维普资讯 http://www.cqvip.com 2OO7年第2期 7 若不然，则所有边对都属于前两组．注 意，由于两条折线各有奇数条边，所以，共有 奇数个边对． 另一方面，对于第一条折线 Z 上的固定 的一条边，它所在的直线与第二条折线 Z，的 交点为偶数个．所以，这条边与 Z 上的所有 边组成的前两种边对的个数为偶数(这里计 数的第二种边对是指延长固定边与 Z 上某 边相交的第二种边对)． 同理，当固定 Z 上一条边时，它与 Z 上 的边组成的前两种边对的个数也是偶数(这 里计数的第二种边对是指延长 Z 上的边与 Z 上的某边相交的第二种边对)． 所有情况相加，总数还是偶数 ． 在这个计数过程中，每个第一种边对恰 被计数 2次，而每个第二种边对恰被各计数 1次．从而，第二种边对的总数为偶数 ． 又因第一种边对与两条折线的交点一一 对应，而 Z 与 Z：的交点数 当然为偶数，所 以，第一种边对的个数为偶数．这样一来，边 对总数为偶数，矛盾． 这表明所求的边对存在． 例 5 已知圆周上有 3 JI}个分点，它们把 圆周分成 3 JI}段弧，其中，长度为 1、2、3的弧 各有 k条．求证：这 3 JI}个分点中必有两点为 对径点(即两点连线为圆的直径)． (1982，全苏数学奥林匹克) 讲解：将给定的 3 JI}个分点都染成红点， 然后增加圆周上的分点，把整个圆周全部分 成长度为 1的弧段，并把新增的分点全部染 成蓝点．显然，蓝点也共有 3 JI}个 ．于是，问题 转化为证明：有一对红点为对径点．为此，又 只须证明：必有两个对径点同色． 若结论不成立，则每个红点的对径点都 是蓝点．在原来的 3 JI}段弧中，任取一段长度 ‘、 为2的AC，于是，点 A、C都是红点，而弧的 中点 曰 是蓝点．由于红点与蓝点同样多且红 点的对径点都是蓝点，故蓝点的对径点也必 为红点．所以，点 B 的对径点 B是红点 ． ‘、 考察长度为 3k一1的AB，设其上长度为 1、2-,3的弧段条数分别为 n。、n：、n，．因为长 度为 1的弧的两个端点都是红点，所以，二者 的对径点都是蓝点．这两个相邻蓝点当然只 能是长度为 3的弧段上增补的两个分点．这 ‘、 样一来，就建立了一个从AB上的长为 1的弧 、 段到BC上的一个长为 3的弧段的对应关系． 显然，这个对应是一个双射． 、 由于BC上的长为 3的弧段条数为 k— n 3，故有 n1=k—n3，即 n1-4-n3=k． 又因 n】-4-2n2-4-3n3=3k一1，所以， 2n2-4-2n3=2k一1． 上式左端为偶数而右端为奇数，矛盾． 4 分组发现新线索，增加新条件 通过分组来显现部分元素所具有的某些 重要性质，发现新线索，增添新条件． 例6 在 11阶图 G中共有n条边，使得 图中既无三角形又无四边形(即 3条边或 4 条边的圈)．求边数 n的最大值 ． 讲解：图 1中共有 11 个顶点和 16条边，且图中 既无三角形又无四边形． 故知所求的边数 n的最 大值不小于 16． 下面证明：若 11阶图 中有 17条边，则其中或有 三角形或有四边形 ． 图 1 若不然，设有一个 11阶图 中有 17条 边，但 中既无三角形又无四边形． 由于 中共有 17条边，故 11个顶点的 度数之和为 34．于是，由抽屉原理知，图中存 在一个顶点 A，使得 d(A)=k>14．设由点 A 引出的 k条边为 AB (i=1，2，⋯，k)，由于图 中没有三角形，故 M={曰 ，曰：，⋯， }的 各点之间均无连线．又因图中没有四边形，故 维普资讯 http://www.cqvip.com 8 中 等 数 学 其余点的集合 Ⅳ={ + ， + ，⋯，B 。}中的 每点至多与 中的点间有 1条连线．这样， 当从图 中去掉 A，B1，B2，⋯， 这 Ji}+1 个点时，至多损失 10条边，余下的以Ⅳ为顶 点集的子图中至少还有 7条边．于是，只须再 证：有 7条边的 6阶图中必有三角形或四 边形 ． 由于这一个 6阶图中有 7条边，故图中 必有圈．由反证假设知，这个圈的边数只能为 5或 6． 若边数为6，则图中还有一条对角线，当 然导致或有三角形或有四边形 ；若边数为 5， 则或者五边形中有一条对角线，或者不在圈 上的第 6个顶点向前 5个点引出两条边，都 导致或有三角形或有四边形． 综上可知，图中边数 n的最大值为 17． 例 7 某国共有 1 001个城市，每两个城 市之间都有单向行车的道路相连通，每个城 市都恰好有 500条出城的道路和 500条入城 的道路 ．在该 国划出一个地区，其中，共有 668个城市．试证 ：由此地区的任何一个城市 出发都可以到达该地区的任何另一个城市， 而无需越出本地区的周界 ． (2o04，俄罗斯数学奥林匹克) 讲解：若不然，则存在此地区的两个城市 和l，，使从城市 出发不能沿着地区内的 道路走到城市l，． 将地区内的全部 668个城市分成 A、B 两组，从城市 出发经区内道路能够到达的 区内所有城市的集合记为A(包括 在内)； 地区内所有其余城市的集合记为 B．显然， l，∈B．所以，A和B都非空． 由于从城市 出发不能到达 B组的任 何一个城市，所以，对于 A和B中的各一个 城市之间的道路，都是从 B中城市走向A中 城市的． ． 设 I A I=a，l B I=b，于是，a+b=668． 不妨设 a≥b(若 b>a，则可改为考察 A 中一个城市的走人线路问题)，于是，a≥ 334．由于每两个城市之间都有单行道且 B 中两个城市之间的单行道当然是从 B中某 城市出发且到达 B中另一个城市的，故由抽 屉原理知，B组中存在一个城市 z，由它出发 1 且到达B中城市的道路至少有去(b一1)条． 二 而由城市 z出发到达A中某城市的道路共 有a条，设由城市z出发的道路总数为z，则 1 1 z≥去(b一1)+a=丢(2a+b一1) 二 二 1 1 = 1(a+667)≥告(334+667)>500， 二 二 此与已知矛盾． 因此，本题结论成立． 例8 设s={1，2，⋯，98}．求最小自然 数 n，使得 S的任何一个 n元子集中都可以 选出10个数，无论怎样将这 l0个数均分成 两组，总有一组中存在 1个数与另外 4个数 都互质，而另一组中总有 1个数与另外 4个 数都不互质． (1998，中国数学奥林匹克) 讲解：首先，s中共有 49个偶数，它们组 成的49元子集显然不满足要求．故知所求的 最小自然数 n>150． 为证 S的任何一个 50元子集 中都有 10个数满足要求，先证明一个加强命题： S的任何一个 50元子集 中必可选出 10个数，使其中的 1个数与另外 9个数都互 质，而另外的9个数两两都不互质． 令 l={2 Ji}l Ji}=1，2，⋯，49}， = {6k一3l Ji}=1，2，⋯，16}， = {5，25，35，55，65，85，95，77，91}， = {7，49，11，13，17，19，23，29，31，37， 41，43，47}． = {1，53，59，61，67，71，73，79，83，89，97}． 显然， 、 、 、眠 、 两两不交， 5 U =5且 维普资讯 http://www.cqvip.com 2O07年第2期 9 I肘1 I=49，I 2 I=16，I 3 I=9， I I=13，I I=11． 设存在 TC S，使得I I=50且使上述加 强命题的结论不成立． (1)若 I n I>t9，由反证假设知，下列 15个奇数 {37，41，43，47}U 5 都不能在 中，故 中至少有 16个偶数． (2)当I n I≤8时， 中的 16个奇 数中至少有 8个不在 中，因此， 中至少 有9个偶数．由反证假设知， n M5= ，故 中至少有20个偶数． 将(1)与(2)结合起来即知，无论如何， 中至少有 16个偶数． (3)当I n ，I≥16时，因为对于 U 中的每个奇数，S中与之不互质的偶数的 个数都不超过7个，故这24个奇数都不在 中．所以， 中至少有 25个偶数． (4)当I n ，I t>25时，因为对于 U U 中的每个奇数，与之不互质的偶数 的个数都不大于 15，由反证假设知，它们都 不在 中，所以， 中至少有34个偶数． (5)当I n ，I t>34时，因为对于 中 的每个奇数，与之不互质的偶数的个数都不 大于 23个，由反证假设知，它们都不在 中，从而， 中没有奇数，此为不可能． 综上可知，所求的最小自然数 ，t=50． 练 习 题 1．试证：可以把由1，2，3，4,5这5个数字各 1个 按任意次序组成的所有五位数分成两组，使得两组 中的数的平方和相等． (1989，全苏数学奥林匹克) (提示：这样的五位数共有 120个．按轮换与对 称性分组即可 ．) 2．平面上给定 m条直线，其中每两条不平行， 每三条不共点．求证：可以将被这 m条直线划分成 的每个区域都标 E一个绝对值不超过 m的非零整 数，使得每条直线的同一侧的所有标数之和都为0． (提示：利用如下引理：可以为 m条直线将平面 划分成的小区域都染上红蓝两色之一，使任何相邻 两块都异色 ．) 3．在一个正方体形方块的表面上用粉笔任意标 出 100个不同的点 ．求证：可以用两种不同的方法将 方块放到黑色板子上(并且使两次所放的位置完全 重合)，使得两次在板子上留下的粉笔印痕有所不同 (如果粉笔标出的点在正方体方块的棱或顶点上，也 同样产生印痕)． (1968，莫斯科数学奥林匹克) (提示：反证并按给定点的所有可能印痕分组， 对给定点为顶点、位于棱上、面中心点及面的非中心 点分别讨论．) 4．求最大正整数 n，使得无论怎样将正整数 1 至400填入 20×20的400个方格中，总有一行或一 列，其中有两数之差不小于 n． (2003，全俄数学奥林匹克) (答案：209．) 5．设自然数 n具有如下性质：在{1，2，⋯，1 988} 的任何一个 n元子集中，总有29个数组成一个等差 数列．求证：n>1 850． (第29届IMO预选题) (提示：先从{1，2，⋯，1 988}中去掉 29的所有倍 数，再把余下的1 92O个数分成 69个子集： A。={29k+j Jj=1，2，⋯，28}(k=0，1，⋯，67)， A鹋={1 973，1 974，⋯，1 988}． 记公差为 d，按(d，29)：1和 d∈{29，58}分两 种情况处理 ．) 6．将数 1，2，⋯， 这 个数任意地分别填入 n×n方格表的n 个方格中．求证：一定存在两个相 邻方格，其中所填的两数之差不小于 n． (第29届INO预选题) (提示：反证．对每个 k=1，2，⋯，／1,2一n，令 表示填有数 1，2，⋯，k的方格所成的集合， 表示 填有k+n，k+n+1，⋯， 的方格所成的集合， 是其余方格的集合．于是，I c‘l-n一1且 A‘中任一 方格都不能与 中方格相邻．由于l c‘l-n一1，故 在 n×n方格表中必有一行和一列方格中没有 中的方格．考察这一行--N方格属于 A‘还是 ，即 可找出矛盾 ．) 维普资讯 http://www.cqvip.com