组合数学辅导讲义08年5月整理的辅导资料.doc

第八讲 组合数学组合数学是中学数学竞赛的“重头戏”，具有形式多样，内容广泛的特点.本讲主要围绕组合计数，组合恒等式及组合最值展开例1圆周上有800个点，依顺时针方向标号为1,2,800它们将圆周分成800个间隙.今选定某一点染成红色，然后按如下规则，逐次染红其余的一些点：若第k号点染成了红色，则可依顺时针方向转过k个间隙，将所到达的点染成红色，试求圆周上最多可以得到多少个红点？解：易见，第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)下的映射计数，尚无较好的结论.例1圆周上有800个点，依顺时针方向标号为1,2,800它们将圆周分成800个间隙.今选定某一点染成红色，然后按如下规则，逐次染红其余的一些点：若第k号点染成了红色，则可依顺时针方向转过k个间隙，将所到达的点染成红色，试求圆周上最多可以得到多少个红点？解：易见，第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),而对k20,kN*，及j5,jN*，由于25+(2k-1)，所以2j+k-2j=2j(2k-1)不为800的倍数.所以，共存在5+20=25个k，满足式。注：本题解法不止一种，但利用些同余理论，可使解法简洁许多.例4S为1,2,n的一些子集族，且S中任意两个集合互不包含，求证：S的元素个数的最大值为(Sperner定理)解：考虑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设M= 1,2,3,2mn (m,nN*)是连续2mn个正整数组成的集合，求最小的正整数k，使得M的任何k元子集中都存在m+1个数，a1,a2,am+1，满足ai|ai+1 (i=1,2,m).解：记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的系数为，因此命题成立.注：构造母函数法，是证明组合问题重要方法之一，但如何找到母函数，是需要长时间的体验的.例8设mn，证明：，其中.证明：当m=n时，上面和式仅有一项，所以.当mn时， .作指标变换：令=k-m，则.所以，原式=,= =0. 注：我们把称为克朗耐克尔，在许多组合恒等证明中，基本的组合恒等式，往往是有力的武器.例9证明：.证明 易证：.因此，由于=,=,所以， .注：此题关键是要找到恒等式，这种裂项的想法需要对组合数相当有“感觉”，也.是重要方法之一.例10设an是一个给定的数列，若bk=，k=0,1,2,an=，n=0,1,2,则称an与bk为一对组合互逆公式，试证明之.证明：考虑，由于=, = ,记，则由于,所以 =, = , = .因此，命题成立.注：利用交换求和及克朗耐克尔，证明了组合变换的互逆公式，在许多组合恒等证明中，十分有用.例11在平面上有n(3)个点，设其中任意两点的距离的最大值为d，我们称距离为d的两点间的线段为该点集的直径，证明：直径的数目至多有n条.证明：引理：平面上n(n3)个点所组成的点集S中，或者存一点至多能引出一条直径，或者任一点至多能引出两条直径.引理的证明：若每一点都至少能引出两条直径，又有一点A能引出三条直径AB、AC、AD，则不妨设AD在AB与AC之间，且必须BAC60o，因此A(d)、B(d)、A CBDC(d)的公共部分覆盖了整个点集S，显然与D能引出两条直径，矛盾!引理得证(如图).下用归纳法证明原体：显然，当n=3时，命题成立，假设命题对k个点成立，则当n=k+1时，如有一点A至多能引出一条直径，去掉A点后，至多还有k条直径，故S最多有k+1条直径，否则任一点至多能引出两条直径，故S最多有条直径，从而命题成立.注：组合几何在研究点集的组合性质时，对一般的图形也可定义直径、半径等.本问题还可推广至三维空间.例12已知：两个非负整数组成的不同集合和.求证：集合与集合相同的充要条件是n是2的幂次，这里允许集合内，相同的元素重复出现.证明：必要性： 构造母函数，.所以 ，所以 ，即.因为 ，所以.所以 存在，使得 ，所以 ，所以 ，所以 .令x=1,则，所以，即n为2的幂次.充分性：直接构造如下中取个，其中 ，中取个,其中，