2013高中数学奥数培训资料之组合数学选讲.doc

兰州成功私立中学高中奥数辅导资料（内部资料）31组合数学选讲组合数学是中学数学竞赛的“重头戏”，具有形式多样，内容广泛的特点.本讲主要围绕组合计数，组合恒等式及组合最值展开例题讲解1圆周上有800个点，依顺时针方向标号为1,2,800它们将圆周分成800个间隙.今选定某一点染成红色，然后按如下规则，逐次染红其余的一些点：若第k号点染成了红色，则可依顺时针方向转过k个间隙，将所到达的点染成红色，试求圆周上最多可以得到多少个红点？2集合X的覆盖是指X的一族互不相同的非空子集A1、A2、Ak，它们的并集A1A2Ak =X，现有集合X=1,2,n，若不考虑A1, A2, Ak的顺序，试求X的覆盖有多少个？3已知集合X=1,2,n，映射f：XX，满足对所有的xX，均有f(f(x)=x，求这样的映射f的个数.4S为1,2,n的一些子集族，且S中任意两个集合互不包含，求证：S的元素个数的最大值为(Sperner定理)5设M= 1,2,3,2mn (m,nN*)是连续2mn个正整数组成的集合，求最小的正整数k，使得M的任何k元子集中都存在m+1个数，a1,a2,am+1，满足ai|ai+1 (i=1,2,m).6计算.7证明： (范德蒙公式)8在平面上有n(3)个点，设其中任意两点的距离的最大值为d，我们称距离为d的两点间的线段为该点集的直径，证明：直径的数目至多有n条.9已知：两个非负整数组成的不同集合和.求证：集合与集合相同的充要条件是n是2的幂次，这里允许集合内，相同的元素重复出现.课后练习1. 空间n条直线，最多能把空间分成多少块空间区域？2. 证明：.3. 证明：.4. 证明：在边长为1的等边三角形内有五个点，则这五个点中一定有距离小于的两点.例题答案：1解：易见，第k号点能被染红的充要条件是 $jN*0，使得a02jk (mod800)，1k800 这里a0是最初染的点的号码，为求最大值，不妨令a0=1.即2jk (mod2552).当j=0,1,2,3,4时，k分别为1,2,4,8,16，又由于2模25的阶，因此，当j5时2j+20-2j=2j(220-1)0(mod 800),而对k0时，每次取两个作为一对，共取j对有种取法.则不考虑j对的顺序，有 .因此，映射f的个数为 .注：这些计数问题，以多次在国际竞赛中出现，但对于一般地情况(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)，则,又然知在时最大，因此当S是由1,2,n中全部元子集组成时，等号成立.注：Sperner定理是1928年发现，证明的方法不止一种.5解：记A=1,2,n，任何一个以i为首项(1in)，2为公比的等比数列与A的交集记为A.一方面，由于M中的2mn-n个元的子集n+1,n+2,2mn中，若存在满足要求的m+1个数：n+1a1a22mn，矛盾，故不存在满足要求的m+1个数，因此所求的k2mn-n+1.另一方面，若k=2mn-n+1时，可证明M中的任何k元子集T中，此有m+1个数a1,a2,am+1满足ai|ai+1 (i1m).反证：假设这样的m+1个数不存在，考虑2i+1为首项，2为公比的等比数列，它与集合M的交的元素个数为|A2i+1|+m，由假设知，它至少有|A2i+1|个元素不在T中，再注意到当ij时，A2i+1A2j+1=f，可知M中至少有个元素不在T中，注意到 所以 ，从而 |T|M|-n2mn-n，这与|T|=2mn-n+1矛盾.故假设不成立.综上所述满足要求的最小正整数值k为2mn-n+1.注：这种先确定单边界限再证明最值是经常采用的.6.解：，作指标变换，令=k-1，则，因此，, = , = .再次用，所以 , =, =.作指标变换，令-1=S，则，所以 = .所以 .注：用利基本的组合恒等式及指标变换，是证明组合恒等式的重要方法之一.7证明：因为的母函数分别为 (1+x)n和(1+x)m而是这两个母函数(1+x)m(1+x)n=(1+x)m+n中xq项的系数，又由于(1+x)m+n中xq的系数为，因此命题成立.注：构造母函数法，是证明组合问题重要方法之一，但如何找到母函数，是需要长时间的体验的.A CBD8证明：引理：平面上n(n3)个点所组成的点集S中，或者存一点至多能引出一条直径，或者任一点至多能引出两条直径.引理的证明：若每一点都至少能引出两条直径，又有一点A能引出三条直径AB、AC、AD，则不妨设AD在AB与AC之间，且必须BAC60o，因此A(d)、B(d)、C(d)的公共部分覆盖了整个点集S，显然与D能引出两条直径，矛盾!引理得证(如图).下用归纳法证明原体：显然，当n=3时，命题成立，假设命题对k个点成立，则当n=k+1时，如有一点A至多能引出一条直径，去掉A点后，至多还有k条直径，故S最多有k+1条直径，否则任一点至多能引出两条直径，故S最多有条直径，从而命题成立.注：组合几何在研究点集的组合性质时，对一般的图形也可定义直径、半径等.本问题还可推广至三维空间.9证明：必要性： 构造母函数，.所以 ，所以 ，即.因为 ，所以.所以 存在，使得 ，所以 ，所以 ，所以 .令x=1,则，所以，即n为2的幂次.充分