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

《高中数学竞赛讲义-组合数学选讲 新人教A 版》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、§30组合数学选讲组合数学是中学数学竞赛的“重头戏”，具有形式多样，内容广泛的特点.本讲主要围绕组合计数，组合恒等式及组合最值展开例题讲解1．圆周上有800个点，依顺时针方向标号为1,2,…,800它们将圆周分成800个间隙.今选定某一点染成红色，然后按如下规则，逐次染红其余的一些点：若第k号点染成了红色，则可依顺时针方向转过k个间隙，将所到达的点染成红色，试求圆周上最多可以得到多少个红点？2．集合X的覆盖是指X的一族互不相同的非空子集A1、A2、…、Ak，它们的并集A1∪A2∪…∪Ak=X，现有集合X={1,2

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的元素个数的最大值为(Sperner定理)5．设M={1,2,3,…,2mn}(m,nÎN*)是连续2m-6-用心爱心专心n个正整数组成的集合，求最小的正整数k，使得M的任何k元子集中都存在m+1个数，a1,a2,…am+1，满足ai

3、ai+1(i=1,

4、2,…,m).6．计算.7．证明：(范德蒙公式)8．在平面上有n(≥3)个点，设其中任意两点的距离的最大值为d，我们称距离为d的两点间的线段为该点集的直径，证明：直径的数目至多有n条.9．已知：两个非负整数组成的不同集合和.求证：集合与集合相同的充要条件是n是2的幂次，这里允许集合内，相同的元素重复出现.例题答案：1．解：易见，第k号点能被染红的充要条件是$jÎN*È{0}，使得a02jºk(mod800)，1≤k≤800①这里a0是最初染的点的号码，为求最大值，不妨令a0=1.即2jºk(mod25×52).-

5、6-用心爱心专心当j=0,1,2,3,4时，k分别为1,2,4,8,16，又由于2模25的阶，因此，当j≥5时2j+20-2j=2j(220-1)º0(mod800),而对"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个，它们共组成了-1个非空子集族.其次，这些子集族中，不合某一元素i的非空子集组成的非

6、空子集族有个；不含两个元素的子集组成的族有个；依次类推，则由容斥原理，X的覆盖共有=个.注：有些组合计数问题直接计数较难，但从反面考虑简洁明了.3．解：设n元中有j个对x、y满足f(x)=y且f(y)=x，其余的满足f(x)=x，则当j=0时，仅一种映射，即恒等映射.当j>0时，每次取两个作为一对，共取j对有种取法.则不考虑j对的顺序，有.因此，映射f的个数为.注：这些计数问题，以多次在国际竞赛中出现，但对于一般地情况(f(n)(x)=x)下的映射计数，尚无较好的结论.4．解：考虑n个元素1,2,…,n的全排列，

7、显然为n!种，另一方面，全排列中前k个元素恰好组成S中的某个集Si的，有k!(n-k)!个，由于S中任意子集互不包含，所以，这种“头”在S中的全排列互不同.设S中有fk个Ai，满足

8、Ai

9、=k(k=1,2,…,n)，则,又然知在时最大，因此-6-用心爱心专心当S是由{1,2,…,n}中全部元子集组成时，等号成立.注：Sperner定理是1928年发现，证明的方法不止一种.5．解：记A={1,2,…,n}，任何一个以i为首项(1≤i≤n)，2为公比的等比数列与A的交集记为A.一方面，由于M中的2mn-n个元的子集{

10、n+1,n+2,…,2mn}中，若存在满足要求的m+1个数：n+1≤a1

11、ai+1(1≤i≤m)，则ai+1≥2ai，从而am+1≥2am≥…≥2ma1≥2m(n+1)>2mn，矛盾，故不存在满足要求的m+1个数，因此所求的k≥2mn-n+1.另一方面，若k=2mn-n+1时，可证明M中的任何k元子集T中，此有m+1个数a1,a2,…am+1满足ai

12、ai+1(i≤1≤m).反证：假设这样的m+1个数不存在，考虑2i+1为首项，2为公比的等比数列，它与集合M的交的元素个数为

13、

14、A2i+1

15、+m，由假设知，它至少有

16、A2i+1

17、个元素不在T中，再注意到当i≠j时，A2i+1ÇA2j+1=f，可知M中至少有个元素不在T中，注意到所以，从而

18、T

19、≤

20、M

21、-n≤2mn-n，这与

22、T

23、=2mn-n+1矛盾.故假设不成立.综上所述满足要求的最小正整数值k为2mn-n+1.注：这种先确定单边界限再证明最值是经常采用的.6.解：，作指标变换，令=k-1，则，因