1 / 7
数学竞赛专题讲座―组合杂题初步
上海中学 (200231)
顾滨
组合问题是数学竞赛中的热点问题，通常也是难度很高的问题．组合问题内容非常广泛，涉及代数，几何以及数论等多个数学分支．组合问题中常见的问题有：组合计数；组合最值；组合几何；组合数论，图论等，其用到的重要原理一般有：抽屉原理；容斥原理；算二次原理；平均数原理；最大（小）数原理．组合计数问题常见处理方法有：枚举法；映射法；算二次法；递推法；母函数法等；组合最值问题常见处理方法：估计法；组合分析法；局部调整法；归纳法；计数法等；组合几何问题常见处理方法：利用凸集；染色赋值法；利用海莱定理,图兰定理等；利用覆盖和嵌入法等．下面，我们来看几个组合问题中典型问题： 1． 有两位棋手在一个无限大的平面上对局，棋子共有５１个，其中只有１匹狼，５０只羊．第一位棋手开局移动狼，然后第二位棋手移动一只羊，接着第一位棋手再移动狼，然后第二位棋手再移动羊，如此下去．若规定狼和羊每次移动可沿任意方向且距离不超过１米，试问：是否有一种初始摆法，使得狼永远抓不住羊？
解：有．在平面上，以米为单位，建立直角坐标系xoy，把５０只羊分别放于５０条直线：
y?3,y?6,y?9,?,y?3?50上，使得每条直线上仅有一只羊，而且开始时，没有一只羊距离狼的距离
在１米之内．由于狼一步至多移动１米，但是任意两只羊之间的距离都大于等于３米，从而，在同一时刻，狼至多只威胁到一只羊，在一对一的情况下，羊沿着直线运动，那么狼不可能抓住羊．
2． 是否存在空间中的５个点，使得对所有的n?{1,2,?,10}，存在两个点，它们之间的距离等于n？
2解：不存在．假设存在这样满足题意的空间５个点，那么它们之间有C5?10个距离，且距离值
1,2,?10仅出现一次，设XY=1,且Z是任意一点，不失一般性，有XZ?YZ
（等号不可能取到,上面已经说明），因此在?XYZ中，由三边关系：XZ?XY?YZ? 0?XZ?YZ?XY?1，因为XZ,YZ都是整数，所以XZ?YZ?1，由此可得X,Y,Z三点共线，进而推得这样的５个点，如果存在，必定共线．
接下去，不失一般性，若存在５个点共线，依次为 A,B,C,D,E，且AE=10，则这１０个距离是：
S?AB?(AB?BC)?(AB?BC?CD)?10?BC?(BC?CD)?(10?AB)?CD?(10?AB?BC)?(10?AB?BC?CD)?40?2BC?2CD
所以，S为偶数，但是1?2???10?55为奇数，矛盾！故不存在．
3． 是否存在两个无差别的骰子，使得这两个骰子点数之和j(2?j?12)的出现概率是(数？
解：设an是第一个骰子出现n的概率，其中n?{1,2,?6}；bn是第二个骰子出现n的概率，其中
n?{1,2,?6}；sn是两个骰子之和出现n的概率，其中n?{1,2,?6}．
23333,4)之间的
若a1b6?a6b1?2a1b1，则s7?2s2，这与s2,s7在()矛盾！所以有0?a1b6?a6b1?2a1b1①； 333324若a1b6?a6b1?2a6b6，则s7?2s12，这与s7,s12在(,)矛盾！所以有0?a1b6?a6b1?2a6b6②；
3333,22由①╳②可得(a1b6?a6b1)?4a1b1a6b6?(a1b6?a6b1)?0，这是不可能的．故不存在这样的两个骰子
24 1
2 / 7
满足题意．
4． 设n是能够被４整除的正整数，在集合{1,2,?,n}上，计算双射f的个数，使得
f(j)?f?1(j)?n?1,j? 1?,2．,n 解：假设j?f(x)，则f(f(x))?则f(x)?x），所以存在y?f(x)，n?1?x（注意既然n为偶数，在我们用函数迭代时候，４个数将形成循环：x,y,n?1?x,n?1?y，x,y,n?1?x,n?1?y,?，在每个循环中，这４个数均不同且恰有２个在集合{1,2,?,}中，所以共有(2nn2?1)(n2?3)?3?1种方法构成数
组(x,y)且每
n4组数将导致２个循环：(x,y,n?1?x,n?1?y)或者(x,n?1?y,n?1?x,y)，因而原问
nn()!n()!nnnn题结果为[(?1)(?3)?3?1]?24，由于(?1)(?3)?3?1?2故化简后值为224．
nn2222()!()!44n5． 设F是所有下列函数f构成的集合：f:P(S)?R，使得对所有的X,Y?P(S)，有
f(X?Y)?min(f(X?)Im(f)表示f的像集．
,1{,}?n．解：对每个n?N*，令Sn?2定义f如下：对每一个A?Sn，若n?A，maxIm(f)?n?1．
f?FfY(，这里S是一个有限集，P(S)是S的子集族，试求：maxIm(f)，其中
f?F则令f(A)?1n?1；
1n 若n?A而n?1?A，则令f(A)?；
．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．； 一般地，若n,n?1,?,k?A，而k?1?A，则令f(A)?X,Y?P(S)，设n,n?1?,n,n?1?,?k,k,?1k，则f是P(S)?R的一个映射，且对
，(k?1,2,?,n?1)，则有?Y)1kX(?，Y而k?1?(XX且,kY?1不同时属于X,Y，于是，由f的定义方式知：f(X),f(Y)?1k至少有一个取
，1即
等号，而f(X?Y)?maIxmf(?)n?． 1f?F，故f(X?Y)?minf(X()f，,Y现在有Imf(?)n?6． 设边长为１的正六边形的六个顶点为P1,P2,?,P6，在其形内（包括边界）任放置两个不同的点P7,P8，求：minPiPj的最小值．
1?i?j?8解：如图所示．可以以Pi为圆心，x为半径作圆弧，则在形内将围成一
2
3 / 7
P3
C
P4
D
E P5
15?3P2 B A F
P6
3个曲边六边形ABCDEF．当x于曲边六边形＂直径＂BE相等时，有122x?2x?()?23，解得x?15?33．若把P7,P8放好时，由于
P1
x?1，所以
1?i?j?8minPiPj＝．若否，存在P7,P8，使得minPiPj＞x，从而P7P8?x，因为曲边ABCDEF直径
1?i?j?8为x,所以，P7,P8中，至少有一个，不妨设为P7，不在曲边六边形形内，但P7在正六边形P1,P2,?,P6形内或者边界上．所以P7必在以Pi(i?1,2,?,6)为圆心，x为半径的某个圆Pi内，不妨设P7在圆P1内，则有P1P7?x与minPiPj＞x矛盾！
1?i?j?8 综上所述, minPiPj=1?i?j?815?33．
7． 设集合S?{1,2,?,50}，X是S的任意子集，且X?n．求最小的正整数n，使得X中必有三个数为直角三角形的三边长．
解：设直角三角形三边长分别为x,y,z，有x2?y2?z2，其正整数解可表示为：x?k(a2?b2)，其中a,b,k?N,(a,b)?1,a?b，则x,y,z中必有一个为５的倍数．若否，y?2kab，z?k(a?b)①，
2则a,b,c都是5m?1,5m?2型的数，所以有a2??1(mod5)；c??1(mod5)，b??1(mod5)，m?N，
222*222而c?a?b?0,?2，矛盾！令集合A={S中所有与5互质的数},则A?40,若以10,15,25,40,45分别作
直角三角形的某边长,则由①知A中找到相应的边构成如下直角三角形：(10,8,6);(26,24,10);(15,12,9);(42,27,36);(39,36,15);(25,24,7);(40,32,24);(41,40,9);(42,27,36)，此外，A中再没有能与10,15,25,40,45构成直角三角形的三条边．令M=A?{10,15,25,40,45}＼{8,9,24,36}，则M?41，有上知A中数不能够成直角三角形，故n?42。下面我们来构造例子：由①知
B＝{3,4,5;15,17,18;29,21,20;25,24,7;34,16,30;37,35,12;50,48,14;41,40,9;45,36,27}可满足，所以B?27，S\\B?50?27?23，在S中任取４２个数，由于42?23?19，所取４２个数中必有含有B中的１９
个数，所以，B中至少有B中一组数，出现在所选的４２个数中，即任取４２个数，满足题意。综上所述，
nmin?42．
8． 把一个n?n的正方形分割成n个小正方形．若可选出n个1?1的小正方形予以标号，使得对一个
2 3
4 / 7
p?q(pq?n)的矩形（其边界或为原正方形的边界或为分割线）内至少包含一个标号的1?1小正方形，
求满足上述条件的正整数n的最大值． 解：nmax?7例子如下：
× × × × × × × 下面假设n?8．考察每一行的1?n矩形，由题意知每行中至少包含一个含标号的方格，又总方格数为n，故每行中恰有一个含标号的方格，每列亦同．设第１行的标号方格位于第k列（1?k?n），由于可将方格翻折，故可设k?讨论：
（１） 若n?2m(m?4)而k?n?12n?1?k2n?12即k?．下面分两种情况
设第k+1列的标号?k?m．
方格位于第j行(1?j?2m)．
①
若j?m，则第m+1行到第2m行及第k列第k+1列构成的2?m矩形中无标号方格（已证每行
每列恰有１个方格）,矛盾！; ②
若j?m?2,则考察第2行到第n+1行及第k列第k+1列的2?m矩形,同理可知矛盾!
故必有j?m?1．再设，第k+2列的标号方格位于第l行，因为m?4，所以k?2?m?2?2m． ① 若l?m?1，则第m+2到2m行及第k列到第k+2列的3?m矩形中，无标号方格，而m?4时
3?(m?1)?2m，矛盾！
② 若l?m?1，同理考察第2行到第m行及第k列到第k+2列知矛盾！综上，n?8得偶数不符合题意； （２） 若n?2m?1(m?4)，而k?n?12?m?1，同理定义j,l可知j?m?1或m?2（考察2?(m?1)的矩形，进一步考察3?(m?1)的矩形，由l知矛盾！）且当m?4时，有3(m?1)?2m，因此n?9为奇数也不符合题意。
综上所述，由(1)(2)知n?8的正整数均不符合题意，故nmax?7．
29． 求满足如下条件的最小正整数n：在圆O的圆周上任取个点A1,A2,?,An，则在Cn个角
?AiOAj(1?i?j?n)中，至少有2007个角不超过120?．
解 首先，当n=90时，如图，设AB是⊙O的直径，在
2点A和B的附近分别取45个点.此时只有2C45?1980
A
· O B
个角不超过120°,所以不满足题意；
当n=91时，下面证明至少有2007个角不超过120?． 对圆周上的91个点，若则连.这样就得到一个圆.设圆中条边，
因为?AiOAj?120?，?AiOAk?120?时，?AiOAk?120?，所以圆G中没有三角形．
4
5 / 7
2若e=0，则有C91?4095?2007个角不超过120，命题得证；
?若e≥1，不妨设A1、A2之间有边相连，因为图中没有三角形，所以对于点Ai(3?i?91)，它至多于A1、A2中的一个有边相连，所以，d(A1)?d(A2)?89?2?91，其中d(A)表示从A处引出的边数．
因为d(A)?1d(Ai)?dA(j?)d(2A?)?而对图G中每一条边的两个顶点Ai,Aj，都有d(9A?)，2e19，于是上式对每一条边求和可得
222(d(A1))?(d(A2))???(d(A91))?91e，
由柯西不等式可得：
91[(d(A1))?(d(A2))???(d(A91))]?[d(A1)?d(A2)???d(A91)]?4e，
22222所以
4e291?(d(A1))?(d(A2))???(d(A91))?91e，即e?2229142?2007
2故９１个顶点中，至少有C91?2071?2024?2007个点对，它们之间没有边相连，从而对应的顶点
所对应的角不超过120°.
综上所述，n的最小值为91.
另解：前面部分相同，下仅证明n?91．不妨设x?y?z．如图所示，下面分情况讨论：
x个点 120o 120o 120o z个点 x个点 Ai
y个点
Ak y个点
①
2y若x?0，1则满足：不超过120?的角１至少有
2zC?C?C?C?2y2zy?z2(y?z)422?2y?z2912?y?z222?912，所以，由柯西不等式得
??2024.75?2007；
②
若x?1，则?AiAjAk中，?AiOAj,?AiOAk,?AjOAk中必有一个
120o 120o 120o 2角不超过120?（平均数原理），而Ai,Aj分别取遍各自区域段中的点，故这样产生的不超过120?的角至少有Cx?Cy?Cz ?x?y?z222222Aj z个点
?x?y?z2?(x?y?z)32?912?2714.8?2007最后一行
的不等式成立是因为柯西不等式，故当n?91时，总可满足题意，从而n的最
小值为91．
练习题
１．能否将正整数１至2002填写到一个2002?2002的方格表中，使得对任何一个方格，或者可以从它
所在的行中，或者可以从它所在的列中找出三个数，其中两个数的乘积等于第三个数？
解：不能．理由如下：数1至2001至多分布在2001行和2001列中，因此必可找到一行和一列，其中所填的数全都不小于2002．于是该行（该列）的任何两数的乘积都大于20022，从而对于位于该行与该列相交处的方格，题中的条件不可能满足．
２．设x1,x2,?,xn?R，且满足?x?n,?xi?s?0．对于0???1证明：这n个数中至少有
i?1i?1?2n2in 5