上海中学顾滨

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

6 / 7

[s(1??)n22]个数大于

?sn．

?s证明：定义A?{j1?j?n,jx?，A为A中元素的个数，由柯西不等式得：}nn2s??x??x??x?iiii?1i?A?iAA??iiAx???iiAx?A?sn?，nA?所以ns(1??)n22，故原命题成立．

３．平面上n（n不为平方数）个点A1,A2,?,An，设??max{AiAj}min{AiAj}，求证：??22[n]

证明：固定d?max{Ai,Aj}．不妨设A1A2?d，分别过A1,A2作半径为d的圆，再过A1,A2分别作切线l1,l2，则存在A1,A2,?,An均在l1,l2之间．再过每个点作垂直于l1,l2的直线，则存在l3,l4，使得所有点在l3,l4之间，又

A1A2AiAj?d，l3,l4之间距离?d，不妨设等于d，则l1,l2,l3,l4交得正方形

A3A4A5A6，则所有点在正方形A3A4A5A6内。再以

l1l2d[2]为边长，将

A3A4A5A6划分成[n]个小正方形，由于n不为正整数，所以n?[n]．所

22以存在一个小正方形内有两个点Ai,Aj，所以minAi{Aj?,}?2，故[n]d??d2?d[n]?22[n]．

４．我们称点集为＂自由集＂如果由集合中点连成的线中不存在等边三角形．证明：平面上n,(n?N)个

点构成的集合，含有＂自由集＂至少有n个．

证明：设f(n)是平面上n个不同的点构成的最大自子集中最小元．我们将证明f(n)?2*n对所有的n2成立．由于f显然是非单调递减函数，所以，只要证明f(n?1)?n?1即可．当我们考虑平面上n?1个点构成的子集，由于这些子集构成的是有限集，我们选一组点，使得在给定的n?1个点中有２个点有相同的x?坐标．设M1,?,Mn22?1是给定的点，且x1???xn2?1，故y?坐标组成了项数为n?1的数列，

2但由于熟知这样的数列有非单调递减数列的n?1项子列或非单调递增的n?1项子列，故不妨设为第一种，

6

7 / 7

设P1,?,Pn?1是满足xi?xi且yi?yj(i?j)时的n?1个点，可得n?1个点构成的集合不可能含有３个点构成等边三角形，因而原问题成立．

7

本文来源：https://www.bwwdw.com/article/lby6.html