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

§30组合数学选讲组合数学是中学数学竞赛的“重头戏”，具有形式多样，内容广泛的特点.本讲主要围绕组合计数，组合恒等式及组合最值展开例题讲解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的元素个数的最大值为nn2(Sperner定理)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).用心爱心专心16．计算n2k1nkk.7．证明：qk0nmmnkqkq(范德蒙公式)8．在平面上有n(≥3)个点，设其中任意两点的距离的最大值为d，我们称距离为d的两点间的线段为该点集的直径，证明：直径的数目至多有n条.9．已知：两个非负整数组成的不同集合},,,{1naaaa和},,,{21nbbb.求证：集合}1{njiaaji与集合}1{njibbji相同的充要条件是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的阶20)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，满足①式。注：本题解法不止一种，但利用些同余理论，可使解法简洁许多.用心爱心专心22．解：首先，X的非空子集共有2n1个，它们共组成了n212-1个非空子集族.其次，这些子集族中，不合某一元素i的非空子集组成的非空子集族有n12121个；不含两个元素的子集组成的族有n22121个；依次类推，则由容斥原理，X的覆盖共有)12()12()12(1221211221nnnnn=)12()1(1201nnjnjj个.注：有些组合计数问题直接计数较难，但从反面考虑简洁明了.3．解：设n元中有j个对x、y满足f(x)=y且f(y)=x，其余的满足f(x)=x，则当j=0时，仅一种映射，即恒等映射.当j>0时，每次取两个作为一对，共取j对有nn2n2j2222种取法.则不考虑j对的顺序，有nn2n2j2n1!(2j1)!!2222jj.因此，映射f的个数为n2j1n1(2j1)!!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)，则nkk1fk!(nk)!n!,又然知nk在nk2时最大，因此当S是由{1,2,…,n}中全部n2元子集组成时，等号成立.注：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，矛盾，故不存在满足要...