第十二讲高中数学竞赛考点组合数学

第十二讲高中数学竞赛考点组合数学

什么是组合数学？组合数学可以一般地描述为：研究离散结构的存在、计数、分析和优化

等问题的一门学科.在不同的阶段有不同的范畴，高中数学竞赛中的组合数学等同于大学里

的离散数学的缩小版，而小学、初中阶段有关组合数学的问题一般称之为杂题。由于组合数

学问题要求的思维品质高，融合的知识广泛，因而成为了各级各类数学竞赛的主要内容。

本讲是针对高中阶段的数学竞赛而设，希望通过以下四个方面的阐述，使大家能对高

中数学竞赛中组合数学问题有一个大致的了解。

一、竞赛说明、考情解读

1、竞赛说明

中国数学会普及委员会对高中数学竞赛制定了考试大纲，即对高中数学教学大纲之外增

加了一部分内容，其中就包含了对组合数学的要求，有圆排列、有重复元素的排列与组合、

组合恒等式、组合计数、组合几何、抽屉原理、容斥原理、极端原理、图论问题、集合的划

分、覆盖、平面凸集、凸包及应用等.

高中阶段各类数学竞赛中的组合数学试题都按上述要求命题，但平面凸集、凸包及应用

等只在CMO中才涉及。

2、考情解读

高中数学竞赛的赛事有：全国高中数学联赛（简称高联）、CMO、IMO、中国东南地区数

学奥林匹克、中国西部地区数学奥林匹克、女子数学奥林匹克等。

组合数学问题的考查情况：在高联中至少有一道填空题和一道解答题，在CMO、IMO中

至少有一道解答题，在中国东南地区数学奥林匹克、中国西部地区数学奥林匹克、女子数学

奥林匹克有二道解答题。

组合数学试题考查常见类型有：组合计数问题、组合极值问题、存在性问题、操作性问

题、组合数论问题、组合几何问题等。

全国高中数学联赛是普及性较高的一项赛事,我们整理了2010-2017近八年的全国高中

数学联赛试题，发现组合数学试题类型分布的情况如下：

20102011201220132014201520162017

组合计数1填空1填空1填空2填空1填空2填空2填空1填空

1解答

组合极值1解答1解答1解答1解答1解答

组合几何1解答

存在性1解答

其中填空题均为一试题（8分），解答题都是加试题（50分）。

一试的组合试题基本是组合计数，加试题重点是组合极值问题，八年中有五年是组合极

值试题，其次是组合计数、组合几何、存在性问题。

组合试题在加试中的位置基本是第三、四道，难度较大，基本是作为压轴题.

另外，由于组合数学的属性，决定了它与数论的结合的比较多，要更好地解决组合数学

问题，必须对数论的相关知识要有一定程度上的掌握。

二、竞赛目标、考点解析

在竞赛中组合数学试题考些什么？跟其他的试题一样，也是考查“三基”，即基础知识、

基本技能、基本思想方法，和它们之间的灵活运用，以及创新能力。但组合数学试题也有异

于其他试题的方面，一是三基交汇重合较多；二是涉及灵活运用和创新能力方面的试题，难

度就会很大，基本是属于压轴题。虽然如此，但我们还是不失一般性，通过列举研究历年高

中数学竞赛真题，为大家展示组合数学试题的考查的六个目标，以期为大家撩开组合数学问

题解决的面纱。

目标一考查组合问题的基础知识

竞赛大纲要求的组合数学的基础知识包括:排列组合二项式定理、组合恒等式、圆排列、

有重复元素的排列与组合、组合计数、组合几何、抽屉原理、容斥原理、极端原理、图论问

题、集合的划分等.

在相关的考试中，只在高联一试中，偏重考查组合问题的基础知识，在高联的加试中

或在其他类型的考试中，虽然会对基础知识有所考查，但更多的是“三基”融合，试题难

度较大。高联一试中组合数学试题的类型主要是组合计数问题.考查的内容从基本的分类、

分步计数原理到排列、组合，从简单的分组、分配到复杂的容斥原理、圆排列、几何计数等，

都有出现.另外也常出现通过概率问题达到考查目标。

例1.（2005年全国高中数学联赛一试试题）将编号为1,2,…，9的九个小球随机放置在

圆周的九个等分点上，每个等分点上各有一个小球.设圆周上所有相邻两球号码之差的绝对

值之和为S.求使S达到最小值的放法的概率.（注：如果某种放法，经旋转或镜面反射后可

与另一种放法重合，则认为是相同的放法）

【解析】（这是一道古典概率题，关键是求出随机试验的样本空间的样本总数和所求随机事

件的样本数。）

先考虑求样本空间的样本总数：九个编号不同的小球放在圆周的九个等分点上，每点放

一个，相当于九个不同元素在圆周上的一个圆排列，故共有8!种放法，考虑到翻转因素，

则不同的放法有三种。

2

下求使S达到最小值的方法种数（即所求随机事件的样本数）：

在圆周上，从1到9有优弧、劣弧两条路径，对其中任一条路径，设

\=X0,X\,X2,--­,xk^=xk+｛是依次排列于该弧上的小球号码，1_____

1=0z=0\

当且仅当1＜%＜一＜々＜9时，等号成立，即而=2x8=16,

9

且这样的放法种数等于

（C；+G+G+日++C；）+2=26=64,故所求概率等于P=

【点评】1、本题考查圆排列数、分类分步计数、组合恒等式等组合数学

有关基础知识；

2、考查了绝对值不等式的性质，要求熟练掌握绝对值不等

式，利用其解决最值，并由此寻找取得最值的放球方法种数；

3、考查了审题能力.

目标二考查组合数学解决问题的基本技能

组合数学解决问题的基本技能：枚举、基本计数（加法、乘法）原理、映射、算两次、

递推、母函数、抽屉原理、容斥原理、极端原理、平均值原理、介值原理等.组合数学之所

以极具魅力，大概缘于她层出不穷的方法技能。

例2.(2010年全国高中数学联赛一试试题)方程x+y+z=2010满足x<y<z的正整数

解(x,y,z)的个数是.

【解析】法1：考虑用枚举法

对x枚举：当％=左(左21)时，由于xWyWz,3k<2010,.,.1<^<670.

~2010-

而y+z=2010-Z:,「.2yW2010-Z:,「.Z:WyW-------,所以％=”时，满

~2010-

足条件的解的个数为---------•一左+1个，因此满足条件的解的总个数为

L2J

。浩行2010—0,八罟「2010—%]爷，sc

S=Y--------------k+1=>-------------->攵+670=336675.

k=\\Ln」Jk=\L4」攵=】

法2：分类计数：把x+y+z=2010满足的正整数解分为三类：

(1)x,y,z均相等的正整数解的个数显然为1；

(2)x,y,z中有且仅有2个相等的正整数解的个数，易知为1003；

(3)设x,%z两两均不相等的正整数解为k.

但我们知x+y+z=201()的正整数解的个数为。纵=2009xl004.

易知1+3x1003+6攵=2009x1004,

所以6%=2009x10()4—3x1003—1

=2006x1005-2009+3x2-1=2006x1005-2004,

B[U=1003x335-334=335671.

从而满足x4y<z的正整数解的个数为

1+1003+335671=336675.

【点评】1、本题考查了分类计数原理等组合数学相关基础知识；

2、考查了枚举、映射、算两次等基本技能和方程的思想。

目标三考查组合数学解决问题的基本思想方法

解决组合问题的基本思想方法有：先猜后证、归纳法、反证法、估计法、计数法、调整

法、组合分析法、配对法、平衡法、染色方法、赋值法等.

竞赛中的组合数学问题，解决她的思想方法深深地隐藏在海洋的深处，必须不断探索，

在一次次挫折与失败中总结经验，才能探明方向。

例3.(2004年全国高中数学联赛加试试题)对于整数〃24,求出最小的整数/(〃)，使得

对于任意正整数加，集合｛以加+1,…,加+〃-1｝的任一个/(〃)元子集中，均有至少3个

两两互素元素。

【解析】(首先要说明/(〃)是存在的)

当“24时，对集合M={/%加+1,…,777+〃-1}:(连续两个正整数是互素的，连续

三个奇数也是互素的)

若则/〃+1,加+2,/〃+3两两互素；若21〃？，则人根+1,加+2两两互素。于是M

的所有〃元子集中，均有至少3个两两互素的元素，于是/(〃)存在且

(其次，估计/(〃)的下限：由m于的任意性，不妨取”={2,3,…,〃+1},构造元素

个数尽量多的M的子集7；,使其任意三个元素都不两两互素，则_/1(”)引口+1)

设(=如《〃+1,且2|t,或3|t},则7；是集合{2,3,…,〃+1}的子集，且该集合中任

意3个元素均不能两两互素，因此/(〃)》园+1。

由容斥原理知：上|=等+等］—［等，从而必有：

(猜测/(〃)的值，并设法证明之)

因此,/(4)>4,/(5)>5,/(6)>5,/(7)>6,/(8)>7,/(9)>8e下证"6)=5

设玉,工2团,工4，尤5为{""+1，…，加+5}中的5个数元素，若这5个数中有3个奇数,

则它们两两互素；(连续六个正整数，那么，奇偶数差的绝对值为1或3或5,若％为偶，y

为奇数，则(％,')=0,%一丁)=(%,k一日)=0,1或3或5))若这5个数中有两个奇数，则

必有3个偶数，不妨设%,％,当为偶数，为奇数，当时，|x,.-xje{2,4},

所以王，/，七中至多有一个能被3整除，至多有一个能被5整除，即至少有一个既不能被3

整除又不能被5整除，不妨设此数为七，则毛，*4，毛两两互素，这就是说这5个数中有3

个数是两两互素，即"6)=5o又由

=1)知：/(H+1)</(n)+l,所以

/(4)=4,/(5)=5,/(6)=5,/(7)=6,/(8)=7,/(9)=8,因此，当4«〃W9时，

C(\「〃+1［「〃+1］「〃+1］,G

/(〃)=----+------------+1。②

\/236

假设当〃=攵(左29)时②式成立，那么当〃=%+1时:

(对集合A=BUCmW忸在A中任取加+〃一1个元素，则一定含有至少m

个B的元素或至少〃个C中的元素。所以对于连续〃个正整数的集合，分成前后两段，分别

为〃।,生个数，则f(n)</(勺)+/(«!)-1)

由归纳假设知〃=6,〃=左一5时②式成立，故：

/伏+1)</(6)+〃%一5)—彳］—［咨+1③

23o

由①③知，当〃=%+1时也成立。

〃+1〃+1

综上可知，对于任意整数”24,都有/(〃)=

"V

【点评】

1、本题考查了容斥原理、抽屉原理等组合数学有关基础知识以及数论的相关基础知识；

2、运用了估计法、构造法、归纳法、先猜后证、数学归纳法、逐步调整法、逼近法等解决

组合问题的基本思想方法；

3、本题解决的重点在于坚持正确的解题方向。

目标四考查组合数学中基本技能、基本思想方法的灵活运用

竞赛中的组合数学的解答题，往往是比较难的问题，需要灵活运用组合数学中的基本技能、

基本思想，经历反复的探索调整，才能把握解决问题的正确的方向.

例4.(第六届中国东南地区数学奥林匹克竞赛试题)设1,2,…,9的所有排列

X—(%),工2,…,不)的集合为A；VXGA>记f(X)—xt+2X2+3x3+…+9为，

M={/(X)|XeA}；求(其中表示集合M的元素个数)

【解析】(显然，/(X)介于1,2,…,9与1,2,…,9的逆序和和顺序和之间，由于

*=(%,%「.,不)有9!个，于是我们猜测/(X)将取遍逆序和到顺序和的所有数。其中有

121个数，我们要用逐步调整手段，找出满足与之对应的121个X,表述非常繁琐。为了有

利于证明，我们采取迂回策略，将其一般化)

我们一般地证明，若〃之4,对于前〃个正整数1,2,…,〃的所有排列X,,=(%,々，…，Z)构

成的集合A,若/区,)=玉+2工2+3七+…+%，M„={/(X)|XeA},则

下面用数学归纳法证明:

n(n+l)(n+2)〃(〃+l)(〃+2)〃(〃+l)(2〃+l)]

n[666J

当〃=4时，由排序不等式知，集合M中的最小元素是/({4,3,2,1})=20,最大元

素是/({1,2,3,4})=30.又，/({3,4,2,1})=21,/({3,4,1,2})=22,/({4,2,1,3})=23,

/({3,2,4,1})=24,/({2,4,1,3})=25,/({1,4,3,2})=26,/({1,4,2,3})=27,

/({2,1,4,3})=28,/({1,2,4,3})=29,

43-4+6

所以，|Mj={20,21,…,30}共有11=--—个元素.因此，〃=4时命题成立.

假设命题在〃一1(〃25)时成立；考虑命题在〃时的情况.对于1,2,—1的任一排列

X.T=(%,工2,…,七-1)，恒取七=〃，得到1,2,…，〃的一个排列七,当,…,尤”_|,〃，

“〃一1〃

则Z2=〃2+工日&.由归纳假设知，此时Z匕■«取遍区间

k=lk=\k=\

/I(/一])〃(”+1),(〃一1)〃(2〃-1)"|n(/i2+5)此±詈斗一所有整数.

H--------------------------=-----------------

"66J[6

再令X"=l，则

力3.=〃+£如=〃+£%(/—1)+吗1)=”(1)+型(/—I),

k=\k=\k=\乙乙«=l

再由归纳假设知，£依人取遍区间

k=l

上的所有整数.

2n(n2+2)n(n2+5)《的偏反而「〃(〃+D(〃+2)〃(〃+1)(2〃+厂

因为-----6---->-----6----，所以，>£取遍区间L------z6--------,--------6--------

上的所有整数.即命题对〃也成立.由数学归纳法知，命题成立.

上丁〃(〃+1)(2〃+1)"(〃+1)(〃+2)〃3—〃+6&人”/3一士人生7

由于———7---------——T-----=——7——，从而，集合的兀素个数为

666

胃―:+6特别是，当”=9时，=

【点评】1、本题运用排序不等式和介值原理进行切入;

2、本题结论很容易猜到，但很难表述清楚，若直接采用调整法，比较繁杂；本解答灵活

运用一般化方法，并用数学归纳法加以证明，并灵活运用了调整法；

3、本题也考查的集合与覆盖等相关的基础知识。

目标五考查组合数学中创新能力型问题

在组合数学中，创新是解决问题的根本源泉，很多看似简单的问题，必须有一个创举才

能得到完美的诠释：很多看似复杂的问题，必须要有所创造才能变得一如的简单.

例5.（2011年全国高中数学联赛加试试题）设A是一个3x9的方格表，在每一个小方格内

各填一个正整数.称A中的一个mx〃（l<根<3,14〃49）方格表为“好矩形”，若它的所有数

的和为10的倍数.称A中的一个1x1的小方格为"坏格”，若它不包含于任何一个“好矩形”.求

A中“坏格”个数的最大值.

【解析】（构造一个尽可能多“坏格”的3x9的方格表，猜测她的最大值）

首先证明A中“坏格”不多于25个.

用反证法.假设结论不成立，则方格表A中至多有1个小方格不是“坏格”.由表格的

对称性，不妨假设此时第1行都是“坏格”.

（对一正整数列%,生，…，见，m<n,则此整数列中一定存在连续几项的和是小的倍

数。因为：记1=£；%,则由抽屉原理知S“中一定有两个数模〃，同余）

/=1

设方格表A第i列从上到下填的数依次为a„h„c„i=1,2,…,9.记

kk

Sk=^a„Tk=£（/>,+c,）,^=0,1,2,•••,9,

i=li=l

这里S°=T0=0.

我们证明：三组数5。百,…偈;"H，…,7；及So+4百+工，…,Sg+T；都是模10的完

全剩余系.

事实上，假如存在〃?,〃，,使5,“三5”（010（110）,贝U

=Sn-S„,三O（modlO）,

i=m+\

即第1行的第〃7+1至第〃列组成一个“好矩形”，与第1行都是“坏格”矛盾.

又假如存在m,n,0<m<n<9,使（“三Tn（mod10）,则

为应+.）=—=0（modl0）,

i=ni+i

即第2行至第3行、第m+1列至第〃列组成一个“好矩形”，从而至少有2个小方格不是“坏

格”,矛盾.

类似地，也不存在,“〃,04"?<〃49,使

Sm+Tm^Sn+T„(mOdl0).

因此上述断言得证.故

999

='XTk三+，.)季0+1+2+…+9=5(modlO)，

k=0k=0k=0

所以

999

Z(5.+，)=+Z.三5+5=O(modlO),

A=()1=0k=0

矛盾！故假设不成立，即“坏格”不可能多于25个.

另一方面，构造如下一个3x9的方格表，可验证每个不填10的小方格都是“坏格”，此

时有25个“坏格”.

综上所述，“坏格”个数的最大值是

25.

1112111110

【点评】1、本题是一个解决问题

的模式很标准的“构造+证明”的

111111111

组合极值问题；

2、创新1111011112之处是在“反证

法”意外地引入“向余理论”，非

常简单导出了矛盾的结论，从而得以证明。

目标六压轴题例

竞赛压轴题考查的目标是：是否能对“三基”进行灵活运用，或能否创造性地解决问题,

或是否经过探究能发现事物的本质特征，从而找到解决问题的方法。

例6：(2009CMO试题)设机，〃是给定的整数，4<m<n,…4“+1是一个正2n+1

边形，P=求顶点属于P且恰有两个内角是锐角的凸m边形的个数.

【解析】

设凸m边形为P\P?…P”,,考虑有一个锐角，不妨设乙P“RP?<%,

――兀P.

更有NP,TP力M>5(34/〈利—1).

而/々6吕+/匕,_£,/>乃，故其中至多一个为锐角，这就说明了顶点在P中的凸m

边形至多有两个锐角，且有两个锐角时，这两个锐角必相邻..

在凸加边形中，设顶点4与4为两个相邻顶点，且在这两个顶点处的内角均为锐角.设

A,与A)的劣弧上包含了尸的厂条边(lWrW〃)，这样的&力在，•固定时恰有2〃+1对.

(1)若凸加边形的其余〃?-2个顶点全在劣弧A,4上，而

劣弧上有r—1个尸中的点，此时这根—2个顶