高中数学竞赛讲义-组合数学选讲 新人教A 版

组合数学是中学数学竞赛的“重头戏”，具有形式多样，内容广泛的特点.本讲主要围绕组合计数，组合恒等式及组合最值展开

例题讲解

1．圆周上有800个点，依顺时针方向标号为1,2,…,800它们将圆周分成800个间隙.今选定某一点染成红色，然后按如下规则，逐次染红其余的一些点：若第k号点染成了红色，则可依顺时针方向转过k个间隙，将所到达的点染成红色，试求圆周上最多可以得到多少个红点？

2．集合X的覆盖是指X的一族互不相同的非空子集A1、A2、…、Ak，它们的并集A1∪A2∪…∪Ak =X，现有集合X={1,2,…,n}，若不考虑A1, A2,…, Ak的顺序，试求X的覆盖有多少个？

3．已知集合X={1,2,…,n}，映射f：X→X，满足对所有的x∈X，均有f(f(x))=x，求这样的映射f的个数.

4．S为{1,2,…,n}的一些子集族，且S中任意两个集合互不包含，求证：S的元素个数的最大值

n为n(Sperner定理) 2

5．设M={ 1,2,3,…,2mn} (m,nN*)是连续2mn个正整数组成的集合，求最小的正整数k，

使得M的任何k元子集中都存在m+1个数，a1,a2,…am+1，满足ai|ai+1 (i=1,2,…,m). 6．计算

2nk. k1knnmmn7．证明： (范德蒙公式)

kqkqk0q

8．在平面上有n(≥3)个点，设其中任意两点的距离的最大值为d，我们称距离为d的两点间的线段为该点集的直径，证明：直径的数目至多有n条.

9．已知：两个非负整数组成的不同集合{a1,aa,,an}和{b1,b2,,bn}.求证：集合这里允{aiaj1ijn}与集合{bibj1ijn}相同的充要条件是n是2的幂次，许集合内，相同的元素重复出现.

例题答案：

1．解：易见，第k号点能被染红的充要条件是

jN*{0}，使得a02jk (mod800)，1≤k≤800 ①

这里a0是最初染的点的号码，为求最大值，不妨令a0=1.即2jk (mod25×52).

当j=0,1,2,3,4时，k分别为1,2,4,8,16，又由于2模25的阶25(2)20，因此，当j≥5时

2j+202j=2j(2201)0(mod 800),

而对k<20,kN*，及j≥5,jN*，由于25+(2k1)，所以

2j+k2j=2j(2k1)不为800的倍数. 所以，共存在5+20=25个k，满足①式。

注：本题解法不止一种，但利用些同余理论，可使解法简洁许多. 2．解：首先，X的非空子集共有2n1个，它们共组成了22n1-1个非空子集族.其次，这些

子集族中，不合某一元素i的非空子集组成的非空子集族有2集组成的族有22n111个；不含两个元素的子

2n211个；依次类推，则由容斥原理，X的覆盖共有

2n11(22n11)(2n11)(2n22n211)=(1)jnj(22j0nn111)个.

注：有些组合计数问题直接计数较难，但从反面考虑简洁明了.

3．解：设n元中有j个对x、y满足f(x)=y且f(y)=x，其余的满足f(x)=x，则 当j=0时，仅一种映射，即恒等映射.

nn2当j>0时，每次取两个作为一对，共取j对有22则不考虑j对的顺序，有

n2j2种取法.

21nn2!j222j2n2n2n2j1 ). !!(2j因此，映射f的个数为1n(2j1)!! . j12j注：这些计数问题，以多次在国际竞赛中出现，但对于一般地情况(f(n)(x)=x)下的映射计数，尚无较好的结论.

4．解：考虑n个元素1,2,…,n的全排列，显然为n!种，另一方面，全排列中前k个元素恰好组成S中的某个集Si的，有k!(nk)!个，由于S中任意子集互不包含，所以，这种“头”在S中的全排列互不同.

设S中有fk个Ai，满足|Ai|=k (k=1,2,…,n)，则

nnfk!(nk)!n!k,又然知在时最大，因此 k2k1kn当S是由{1,2,…,n}中全部元子集组成时，等号成立.

2注：Sperner定理是1928年发现，证明的方法不止一种.

5．解：记A={1,2,…,n}，任何一个以i为首项(1≤i≤n)，2为公比的等比数列与A的交集记为A.

一方面，由于M中的2mnn个元的子集{n+1,n+2,…,2mn}中，若存在满足要求的m+1个数：n+1≤a12mn，矛盾，故不存在满足要求的m+1个数，因此所求的k≥2mnn+1.

另一方面，若k=2mnn+1时，可证明M中的任何k元子集T中，此有m+1个数a1,a2,…am+1满足ai|ai+1 (i≤1≤m).

反证：假设这样的m+1个数不存在，考虑2i+1为首项inn1，2为公比的等比数列，2它与集合M的交的元素个数为|A2i+1|+m，由假设知，它至少有|A2i+1|个元素不在T中，再注意到当i≠j时，A2i+1A2j+1=，可知M中至少有

1i|A2i+1|个元素不在T中，

n-12注意到

1in12A2A 所以 |M\\S|i11in12A2i+1|A|n，

从而 |T|≤|M|n≤2mnn，这与|T|=2mnn+1矛盾.故假设不成立.

综上所述满足要求的最小正整数值k为2mnn+1. 注：这种先确定单边界限再证明最值是经常采用的.

nnn2nn1n1n6.解：kknk，作指标变换，令l=k1，则1klkk1k1k1k1kk1n2n10，

因此，

kk(l1),

n1k1n1ln1lk1l0nl0nn1n1 =

lk,

n1ln1lk1l0n1 =

l2n1lk1nn1.

nnn1再次用，所以

kkk1ll0n12n1ln1ll0n1n1l2n2l1n1,

=

(n1)2n2l1l1n1l1n2l1n1n1,

=(n1)2n1.

n1作指标变换，令l1=S，则，1lsn1l1n20所以

(n1)2n2l1n1=(n1)2n2ss0n2n2n1

(n1)2所以

2n1.

.

2nkn(n1)2n2n2kk1n2n1n(n1)2n注：用利基本的组合恒等式及指标变换，是证明组合恒等式的重要方法之一. 7．证明：,qnmnm

因为的母函数分别为 (1+x)和(1+x)

kknmmnm+nqm+nq

而是这两个母函数(1+x)(1+x)=(1+x)中x项的系数，又由于(1+x)中x的k0kqk系数为mn，因此命题成立.

q注：构造母函数法，是证明组合问题重要方法之一，但如何找到母函数，是需要长时间的体验的.

8．证明：[引理]：平面上n(n≥3)个点所组成的点集S中，或者存一点至多能引出一条直径，或者任一点至多能引出两条直径.

[引理的证明]：若每一点都至少能引出两条直径，又有一点A能引出三条直径AB、AC、AD，则不妨设AD在AB与AC之间，且必须BAC≤60o，因此⊙A(d)、⊙B(d)、⊙C(d)的公共部分覆盖了整个点集S，显然与D能引出两条直径，矛盾!引理得证(如图).下用归纳法证明原体：

显然，当n=3时，命题成立， 假设命题对k个点成立，则当n=k+1时， 如有一点A至多能引出一条直径，去掉A点后，

至多还有k条直径，故S最多有k+1条直径，否则任一点至多能 引出两条直径，故S最多有

C

A · ·D

· B

2(k1)k1条直径，从而命题成立. 2注：组合几何在研究点集的组合性质时，对一般的图形也可定义直径、半径等.本问题还可推广至三维空间.

9．证明：必要性： 构造母函数f(x)xa1xa2xan，

g(x)xb1xb2xbn.

所以 f(x)f(x)2222221ijnxaiaj，g(x)g(x)2222221ijnxbibj

2所以 f(x)f(x)g(x)g(x)，即f(x)g(x)f(x)g(x). 因为 f(1)g(1)0，所以x1f(x)g(x).

所以 存在hN，使得 (x1)P(x)f(x)g(x),P(x)0，

222h2h2所以 f(x)f(x)(x1)P(x)，

所以 [f(x)g(x)](x1)P(x)(x1)P(x)，

h2h2(x1)hP(x2)所以 f(x)g(x).

P(x)令x=1,则2n2，所以，n2充分性：直接构造如下

1{a1,aa,,an}中取k2l个2l，其中 l0,1,,[hh1，即n为2的幂次.

k11]，{b1,b2,,bn}中取k2l1个 2k2l1,其中l0,1,,[]，则这两个集合满足要求.

2注：运用母函数处理集合问题，是常见的方法，尤其注意这种集合中出现在指数上而不是系数上的母函数方法.