张佳
(天津师范大学数学科学学院2019级硕士研究生,300387) 中图分类号:〇141.2 文献标识码：A文章编号=1005 - 6416(2021)05 - 0007 - 05
(本讲适合高中）
组合数学历史悠久，早在几千年前就已经出现了一些有趣的组合问题，在日常生活 中随处可见.在解决组合问题时所产生的数学方法对数学的研究具有深远意义，而之前 已出现的数学方法更对解决组合问题具有重 要影响.本文归纳出常用的一些解题方法. 1数学归纳法
数学归纳法在竞赛数学方法中占重要地 位，也是解决组合问题最常用的一种方法.
当需要证明/I时此种结论是成立的，可 以分两步证明：先证明n= l时结论成立，再 假设n= m - 1时结论成立，以此推出/I = m 时结论成立.
在竞赛数学中，通过个例或特例推导出的结论可能成立也可能不成立，这就需进一 步检验或证明，通常采用数学归纳法证明.
例1已知平面上的n(n多4)个点任意
收稿日期:2021 -01 -25三点不共线，任意两点之间连一条线段.求不 与其他任何线段相交（端点除外）的线段数目的最大值.[1]
(第23届土耳其数学奥林匹克）
【分析】当r a = 4时，不与其他任何线段相交（端点除外）的线段数目的最大值为6, 如图1.
图1图2
当n =5时，不与其他任何线段相交（端 点除外）的线段数目的最大值为8 ，如图2.
对于〃个点的凸包为三角形，不妨考虑正•设其中心为0, A B O C的外接圆
在内的弧&上，任意取n - 3个点£)1，仏，"_，/)…_3，则这；1个点^4,5"1，1)2,…，h_3满足条件的线段为
岑=丨1，2,5,7，10丨，
4 = 11,4,5,7,9!,
>14 = {2,3,4,7,9|,
A5 = |3,4,5,8,1〇!.
令4= U(10A+為）（i= 1，2,…，5)即可.
k=Q
参考文献：
[1] 2014年全国高中数学联合竞赛[J].中等数学,2014
(11)：20,
[2]《中等数学》编辑部编•国内外数学竞赛题及精解
(2017—2018) [M].哈尔滨：哈尔滨工业大学出版社，
2019,6:42,67,184.
[3] 2015年全国高中数学联合竞赛[J].中等数学，2015
(10:29.
[4]刘培杰数学工作室编.历届中国东南地区数学奥林
匹克试题集:2004 ~2012[M].哈尔滨：哈尔滨工业大
学出版社，2014,6.
[5]冷岗松主编.数学竞赛问题与感悟（第二卷：研究文
集）[M].上海：华东师范大学出版社,2019,4:69-71. [6] 2013罗马尼亚国家队选拔考试[J].中等数学,2014
(增刊二）：
170.
8
中等数学
AD 2,-,ADn _…BDx ,Dx D 2,D 2D ,,-,Dn _,D n_,, A __3C ，共有2〃-2条.通过举例得到平面上 的n 个点满足条件的线段数目的最大值，再 由数学归纳法证明结论.
证明设5…为满足条件的线段数目.
下面证明:S …ミ2/^-2•当n =4 时 ，结论显然成立.先假设n 时结论成立，则有
- 2.
对于n + 1时，若n + l 个点的凸包为凸
n + 1边形，则
^n + \ =n + \ ^2(n + 1 )-2，结论成立.
若n + 1个点的凸包厂不是凸n + 1边 形，则在凸包尸内存在一点P ，对于其余/I 个 点，将凸包尸进行三角形剖分，每个剖分出 的小三角形的顶点为已知的n 个点中的点， P 在剖分成的一个三角形内，不
妨假设点P 在
内
.
若删去点/1，由归纳假设知&矣2n -2.(1)
若有一条边不满足条
件，不妨设C 4不满足条件，则存在线段£F ， 其与C 4在内部相交，将点P 加人时，线段 W —定与/M 或P C 之一相交.故
Sn + 1^Sn + 2<2(n + l )-2.(2)
若M 、fiC 、C 4均满足条件，由n + 1 >5，知在之外仍有一点(?，线段
一定与A A B C 的三边之一相交，不妨假设
八？与C /1相交.故
S n+1 ^5n + 3 —1 ^2(/i +1) — 2.
因此，的最大值为2n -2.2
反证法
反证法是数学解题中的重要证明方法， 也是解决竞赛数学中组合问题的有效手段. 通过断定与命题相矛盾的判断，推出与条件 矛盾的结论，从而证明原命题结论成立.在解 决数学问题时，从正面不容易证明或无法证 明时，就需要用反证法来证明.
原命题条件很少时，可以利用反证法得
到相反的判断，在此判断下就增加已知条件， 有时候相反的判断会出现有很多种情况，就 需要将所有的情况一一证明矛盾，由此证明 原结论成立.
例2
已知一个简单多边形尸（不自交，
但不必要是凸的）.证明：存在尸的一条全在 多边形尸内部的对角线，其将r 的边界分成 两个多边形，每个小的多边形的顶点的个数至少为r 的顶点个数的f .[2]
(2006，伊朗国家队选拔考试）
【分析】设多边形厂为n 边形.对于r 的 任意一个三角形剖分，将小三角形视为图c 中的一个点.若两个小三角形相邻，则在这两 个小三角形对应的点之间连一条边.故图c 中点的个数为A ： = ra -2，边的数目为ra -3，且 每个点的度^满足1
矣3•又C 为一棵连
f型钢
通树，只要证在图G 中存在一^条边，删去这 条边得到两个子图^、G 2，则G i 、G 2中的点
的
个
数
均
至
少
为
= I - 2).
钢筋剥肋滚丝机证明假设结论不成立，删掉任意一条
边后得到的子图中的点的个数要么小于
要么大于^^ .对于图G 中的任意一个顶点u ，设u 的
三个连通分支分别为7\、:r 2、:T 3,7\、:r 2、:r 3
中的顶点的个数分别为，不妨设
于是…一士要么均小于^^要么均大「2“ 4
若 h < 4^，贝丨J 外 X 3.
故 A ： = L + 艺 2 + 6 + 1 <3
+ l =k -3,
矛盾.
2021年第5期9若则
2k+ A
:h + 艺2 + ,3 + 1 > 2 x—-—+ 1 > A：,拳击架
矛盾.
从而，一定有 q>~--^,t2j3•
淤泥固化设7；中唯一的顶点/(«)与u相邻，类
似可得
U —f(u) 一 f(f(u)) 4 ….
因为G是一■棵树，所以，一'定存在G中
的一个顶点I使得
f(f(v)) = V.
故k>2k+4
3
+2-%t4>&，矛盾.
综上，每个小的多边形的顶点的个数至
假设存在一点4，引出不少于四条红边，不妨假设仙,、狀2、从3、狀4为红边.则A、氏、fi3、fi4两两相连的边一定均为蓝.
从而，得到蓝的结论成立.
否则，每个点最多引出三条红边，则每个 点均至少引出五条蓝边.
若每个点均恰引出五条蓝边，则蓝边的数目为矛盾.
因此，一定存在一点C引出至少六条蓝边，不妨设为，…，c z v
对于点A，込，…，z>6，由拉姆塞定理，知 一定存在同三角形且为蓝三角形.
不妨设A A込仏为蓝三角形，则得 到蓝的&，结论成立.
少为厂的顶点个数的|.
3分类讨论
数学中任何一种结论的产生都有其成立 的条件；任何一种数学方法都有其适用的范围.有些命题的结论并不能用统一的方法证明，有时候需要把研究的问题按照命题的要求分类，化成几个小问题，从而使问题得到解 决，这就是分类讨论.分类讨论可以使复杂问 题简单化、条理化，为深入研究数学问题，特 别是数学竞赛中的组合问题创造了条件.这不仅在数学概念和定理的学习上十分重要，在解决数学问题时也起到重要作用.
例3任意九个人要么有三个人认识，要么有四个人互相不认识.
【分析】将九个人对应成九个点.若两人认识，则在对应点之间连一条红边；若两人不 认识，则在对应点之间连一条蓝边，得到一个 图.只要证要么存在一个红的&，要么存 在一个蓝的则可分成存在红的&、不存在红的尺3这两种情况进行讨论.
证明（1)若存在红的尺3，结论成立•
(2)若不存在红的尺3.4奇偶分析
对于整数，所有的奇数可以用技+ 1表 示，所有的偶数可以用2A表示，其中，为整 数.在解决竞赛数学中的组合问题时，有时候 对问题中的量分析其奇偶性，利用整数奇偶的性质可以快速解题.
例4求所有的正整数对（m,n)，使得可以将w i x/i方格表中的每一个单元格染成白或黑，并满足：对于每一个单元格4，与该单元格4至少有一个公共顶点且与4同 的单元格（包括4本身）有偶数个.[3]
(2〇05，丝绸之路数学竞赛）
解称满足条件的染法为“好的”，称至 少有一个公共点的两个单元格是“相邻的”，每个单元格与自身是相邻的.
若/rm为偶数，假设有偶数行，可将第1、2行染白，第3、4行染黑，第5、6行染白，……如此交替进行染，则易知这样的 染法是好的.
若为奇数，假设存在一种好的染法，则要么白的单元格有奇数个，要么黑的单元格有奇数个.不妨设白的单元格有奇数个.
10中等数学
接下来考虑所有的由两个不相邻的白 的单元格组成的有序对构成的集合R
因为每个单元格与自身是相邻的，所以，若M，B)e w w f i)，则
(B,A)e w.
从而，集合取中的元素有偶数个•
又由于白的单元格有奇数个，对于每 个白的单元格有奇数个与其不相邻的白 的单元格（因为与其相邻的单元格有偶数个），从而，可得集合妒中有奇数个元素，矛盾•综上，满足条件的正整数对（m,n)应满 足m n为偶数.
【注】奇偶分析并不适用于任意有数量的题，有些题使用奇偶分析会使解题过程更加复杂，为此，在做题时需要结合题目选择更 好用的方法.
5递推
递推是一种重要的数学思想，在竞赛数学的组合问题中被广泛运用.在解决数学问 题时，若可以到相邻数据的关系即递推关系，则可使用递推方法，从而，把一个复杂问 题的求解简化为若干重复步骤的简单运算.
例5将一个2 003边形的每个顶点染 为红、蓝、绿三种颜之一，使得相邻顶点的颜互不相同.问：有多少种满足条件的染法?[3]
(2002—2003，匈牙利数学奥林匹克）
解设是将一个n边形的每个顶点染为红、蓝、绿三种颜之一，使得相邻顶点的颜互不相同的染法的种数.
易知，r3 =6，T4 = 18.
对于任意一个n()，记4，岑，…，疋顺次为该n边形的顶点，则对其按题设要求染，分两种情况：
(1) 枣人4异，共有种;
(2) ^、^^同，共有27；_2种.
则7>7；_1+27；_2(05).
又 713=6,7；=18，于是，
Tn =2(-l)B +2".
从而，r2003=22003 -2.
例6给定一个由字符“〇”与“◊”组 成的字符串用4(5)表示字符串S中“
的个数与“〇”的个数的差（例如，A(◊〇〇◊〇〇◊) = -1).若字符串S的 每一个子串r满足-2爸4(r) <2，则称字符 串s是“平衡的”（子串是字符串s中若干个 连续的字符组成的串）.求长度为《的平衡 字符串的个数.[3]
(2007，印度国家队选拔考试）
解用表示长度为n的平衡字符串 的个数.
接下来证明:6...+2=26 (2)
当n= l时，平衡字符串为〇或◊，故
bx =2.
当n =2时，平衡字符串为◊◊，◊〇，〇◊，〇〇，故
b2 =4.
当^=3时，平衡字符串为◊◊〇，◊〇◊,◊〇〇，〇◊〇，〇◊◊，〇〇◊，故—6.
当n = 4时，平衡字符串为◊◊〇◊，◊◊〇〇，◊〇◊◊，◊〇◊〇，◊〇〇◊，〇◊〇◊，〇◊〇〇，〇◊◊〇，〇
〇◊◊，〇〇◊〇，故
64=10.
用分别表示长度为〃的平衡字符串中以◊◊结尾的n位平衡字符串数、以◊〇结尾且最后一个连续两位重复字符串为◊◊的〃位平衡字符串数、以◊〇结尾且最后一个连续两位重复字符串为〇〇的〃位平 衡字符串数.
注意到，平衡字符串中，◊与〇可以“角 互换故〜也可以表示以〇〇结尾的n
位平衡字符串数，；也可以表示以〇◊结尾 且最后一个连续两位重复字符串为〇〇的n 位平衡字符串数，\也可以表示以〇◊结尾 且最后一个连续两位重复字符串为◊◊的^
2021年第5期11
位平衡字符串的个数.
因此，= 2x…+ 2y…+ 2z…+ 2 (增加…和…〇◊〇◊〇◊)，即
b n-2 =2(xn +yn +z n).
基于上述讨论，可在〃位平衡字符串的
基础上构造出n+ 2位平衡字符串.
(1) 若原n位平衡字符串以◊◊结尾，只可添加〇〇或〇〇.
(2) 若原n位平衡字符串以◊◦结尾，且最后一个连续两位重复字符串为◊◊，只
可添加〇◊*◊〇.
电暖手套
(3) 若原n位平衡字符串以◊〇结尾，且最后一个连续两位重复字符串为〇〇，只
可添加◊〇或
(4) 若原71位¥»符串为...◊〇◊〇◊〇，只可添加◊〇或〇◊或
类似可得◊与〇互换后的情况.
故^*+2 =2(2(〜+yn +\)+3)
= 2(bn -2) + 6 =26… +2
^b2n=3x2n-2,b2n_l=2n+l-2.
组合数学不仅在基础数学研究中具有重
要的地位，在其他学科中也有重要的应用，竞
赛数学中组合问题的方法还有很多，有时候
同一道题也会有多种方法需要继续学习总结.
练习题
1.设n j G Z+，且已知某国共有
n座城市，且每两座城市之间均有一辆公交
车可双向行驶.证明：从城市4恰乘坐&辆公
交车到达城市5的方法数为士止.
TJA1100n
(2011，荷兰国家队选拔考试）
提示记从城市4乘坐&辆公交车到达
城市扒的方法数为a(A)，从城市4乘
坐辆公交车到达城市4的方法的数为)8(幻.
易知，从城市4出发乘坐一辆公交车灸
次，有U-l)4种方法.同时若回到城市4有
月(幻种方法，若到达不同于城市4的城市有
(n-l)a U)种方法，则/3(k)+(n-\)a(k)=(n-l)k.①设A：多2.易知，
将々(&) = (ra- 1)〇:(& - 1)代人式①，知
当A：多2时，
(n-l)a(A：-l)+(ra-l)a(A：)=(n-l)4
=> a(k)= (n - l)k~' - a(k -.
接下来对&用数学归纳法即可证明结论
成立.
2. 在9x9方格表中，有46个格被染上红.证明：在此方格表中，存在一个2 x2小
方格表，其中至少有三个红格.
(2011，新加坡数学奥林匹克）
提示反证法.假设任意一个2x2小方
格表至多有两个红格，则可看成任一个9 x 2
小方格表中至少有十个红格•考虑八个2 x2
小方格表中的红格数，可推出假设与条件矛
盾，即结论成立.
3. —个（《 - 1)x 〇 - 1)方格表被分成
(-1)2个单元格，这些单元格的n2个顶点中
的每一个被染为红或蓝.求不同的染
方法的数目，使得每个单元格的顶点中恰有
两个红的点（在两种染方法中，至少有
一个点被染的颜不同就认为是两种不同的
染方法).
(2008，意大利数学奥林匹克）
提示第一行的染情况有两种：要么
两种颜交替出现，要么有两个相邻的点同
.分别讨论这两种情况的染方式即可得
到结论.
4.A：枚棋子置于一个r a x re(re多2)方格
表中的A个格中（每个格恰有一枚棋子），且
在每一个2 x2子方格表中恰有两枚棋子•求
所有可能的&值.
(第62届白俄罗斯数学奥林匹克）
提示利用奇偶分析法：当》为偶数时，
将n x n分割成m2 = ^个 2 x2子方格表，从
每一个2 X2子方格表中恰有两枚棋子求得
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议