老年人食品-小学五年级语文上册教案

组合数学论文

竞赛数学中的组合数学问题

















第1页

竞赛数学中的组合数学问题
组合数学是上个世纪五十年代后逐步建立和完善起来的一 门数学分支，组合
数学也称为组合学、组合论，组合分析。教科书上对组合分析的定义：按某种要
求把一些元素构成有限集合的研究叫做组合分析。
这种研究比传统的数学讨论的对象更广泛 ，在实际生活和实践活动中应用性
更大。这种研究一般讨论以下问题：在一定的约束条件下，对象——构 成的存在
性（有与没有、能与不能）问题；构成的分类与计数；构成的方法（构造方法）
及最优 化方法。
人们常把竞赛中某些问题称为杂题，又称为组合数学问题。为什么？
中学数学竞赛中的一些问题，很难把它们归类为代数问题或几何问题，但它
们涉及到的解题目标和解题方 法可以归入组合问题和组合分析；当然一些组合数
学的习题也直接用作竞赛题。
初等数学竞赛 中的组合问题与组合分析常用的方法有抽屉原理、递推（归）
原理、容斥原理、染色方法等，这些原理方 法都很一般，重要的是经验和技巧——
应用的能力。本文重点研究竞赛数学中的组合数学计数问题。
计数问题
组合数学中的计数问题，数学竞赛题中的熟面孔，看似司空见惯，不足为
奇 ．很多同学认为只要凭借课内知识就可左右逢源，迎刃而解．其实具体解题时，
时常会使你挖空心思，也 无所适从。对于这类问题往往首先要通过构造法描绘出
对象的简单数学模型，继而借助在计数问题中常用 的一些数学原理方可得出所求
对象的总数或其范围。
1、计数中求最大值：
第一步：分类讨论
（1）情况一，推出目标数 f ≤m
1
；
（2）情况二，推出目标数 f ≤m
2
；
„
（s）情况s，推出目标数 f ≤m
s
；
第二步：m
0
=max{m
1
，m
2
，…，ms
}，则f ≤m
0
；
第三步：构造模型使计数恰好等于常数 m
0
，则常数 m
0
即为最大值。
另一种叙述:
第1步：由目标数 f ≤m推出可以符合条件；
第2步： 由f =m+1推出是不能符合条件；
所以 f
max
= m 。


2、计数中求最小值：
第一步：分类讨论
（1）情况一，推出目标数 f ≥m
1
；
（2）情况二，推出目标数 f ≥m
2
；
„
（s）情况s，推出目标数 f ≥m
s
；
第二步 ：m
0
=min{m
1
，m
2
，…，m
s
}，则f ≥m
0
；
第三步：构造模型使计数恰好等于常数 m
0
，则常数 m
0
即为最小值。
另一种叙述:
第一步：由目标数 f ≥m推出可以；

第2页

第二步：由目标数f =m－1推出不能；
所以

f
min
=m

。

下面我们从一道简单的组合问题说起：
如图，每个正方体的六个面上分别写着数字1，2，3 ，4，5，6，并且任意
两个相对的面上所写的两个数字之和都等于7。把这样的4个正方体一个挨着一
个连接起来后，紧挨着的两个面上的数字之和都等于8。图中标着 x 的那个面
上所写的数字是几？
分析：
拐角处正方体前后分别为4，3，则右侧面 可能是1或6，
而1不能使x面的对面数字为7，故只能为6，所以x的对
面数字为2，所以， x =5。

著名的赛题 图1
证明：任意六个人中，总有三个人，要么相互认识，要么相互不认识。
同色分析三步：把实际问题转化为图形染色；抽屉原理；二分法推理。
证明：
圆上 六个点A
1
A
2
A
3
A
4
A
5< br>A
6
表示六个人，两人相
互认识，相应两点间连红线，两人不相识，相应两点间
连蓝线，原命题即为证明存在三边同色的三角形。与
A
1
相连的5条线分别染 两种颜色，至少有三条线同色。
不妨设至少有三条红线，且为A
1
A
2
、A
1
A
3
、A
1
A
4
。若
A
2
、A
3
、A
4
三点间的连线有一条红线，则有红色三角< br>形；否则，三条连线都是蓝线，存在蓝色三角形。
图2
例1、由9位裁判给参加健美比赛的12名运动员评分。每位裁判对他认为的第
一名运动 员给1分，第二名运动员给2分，„，第12名运动员给12分。最后评
分结果显示：每名运动员所得的 9个分数中高低分之差都不大于3分。设各运动
员的得分总和分别为e
1
，e
2
，e
3
，…，e
12
，且e
1
≤e
2< br>≤e
3
≤…≤e
12
，求e
1
的最大值。
分析：含1分的格子最多有4列，此4列的每格数字平均不超过22.5，3列呢？
2列？1列？
解：
对9个1分布的列数进行讨论：
（1）1分分布在同一列，该列的和为 9，e
1
= 9；
（2）1分恰在两列中，列中数字不超过4，两列的
和最 大为5×9=45，较小的列和≤45÷2，是整数，
则较小的列和≤22， 故最小的列和e
1
≤22(21)；
（3）1分恰在三列中，列中数字不超过4，三列的
和最大为8×9=72，同理 e
1
≤24；
（4）1分恰在四列中，列中数字不超过4，四列的
和最大为10×9=90，同理 e
1
≤22； 图3
（ 5）1分恰在5列中，5列45个数都只能取1、2、3、4，9个裁判只能给出9
个1、2、3、4， 共36个，填不满5列；同理，1分不能分布在比5更多的列中。
所以，1最多能在4列中。故 e
1
≤24。

第3页

若前三列中， 每列三个1、三个3、三个4，每列的和都是24，第四列5个2，4
个5，和为30；第五列4个2， 5个5，和为33；以后第
k
列填9个
k
，和为9
k
≥54 。
则 e
1
=24。所以e
1
的最大值为24。
例2、 有两副扑克牌，每副牌的排列顺序是：第一张是大王，第二张是小王，然
后是黑桃、红桃、方块、梅花4 种花色排列，每种花色的牌又按A，2，3，„，
J，Q，K的顺序排列。某人把按上述排列的两副扑克 牌上下叠在一起，然后从上
到下把第一张丢掉，把第二张放在最底层，把第三张丢掉，把第四张放在最底
层„„，如此下去，直至最后剩下一张牌。则所剩的这张牌是什么？
我们先来看下下面这道题，是一个小学的竞赛题，称为“做数学”。
依顺时针方向将数字1， 2，3，4，5，6，7写在圆周上。首先将数字1删除，
然后每次跳过一个未删除的数，删除被跳到位 置上的数，依此方法继续进行直到
最后只剩下一个数为止。例如，
删除数字1，跳过数字2；
删除数字3，跳过数字4；
删除数字5，跳过数字6；
删除数字7，跳过数字2；
删除数字4，跳过数字6；
删除数字2，所以，剩下最后的一个数是6。 图4
如果依顺时针方向将 1，2，3，„，2004写在圆周上，并依照上述规则操作，
试问最后剩下的一个数为 。
解：
第一圈:从1开始，删去所有奇数，余下2k型数：
2，4，6，8，„，2002，2004；
第二圈:从2开始，删去所有4k-2型数，余下4k型数：
4， 8，12，16，„，2000，2004；
第三圈:从4开始，删去所有8k+4型数，余下8k型数：
8，16，24，„，1992，2000；
第四圈:从16开始，删去所有16k型数，余下16k-8型数：
8，24，40，„，1976，1992；
第五圈:从24开始，删去所有32k-8型数，余下32k-24型数：
8， 40，72„，1960，1992；
第六圈:从8开始，删去所有64k-56型数，余下64k-24型数：
40，104，„，1896，1960；
第六圈:从8开始，删去所有64k-56型数，余64k-24型数：
40，104，„，1896，1960；
第七圈:从104起，删去所有128k-24型数，余128k-88型数：
40，168 ，296，424，552，680，808，936，1064，1192，1320，1448，1576，
1704，1832，1960；
第八圈:从40起，删去所有256k-216型数，余256k-88型数：
168， 424， 680， 936， 1192， 1448， 1704， 1960；
第九圈:从168起,删去所有512k-344型数，余512k-88型数：
424， 936， 1448， 1960；
第十圈:删去424，1448，余下：936， 1960；
最后，删去936，余下1960 。

第4页

分析：下面我们回顾刚才那道题，也来“做数学”。
解：
依次把牌编为1，2，3，„，108；
第一圈:从1开始，删去所有奇数，余下2k型数：
2，4，6，8，„，108；
第二圈:从2开始，删去所有4k-2型数，余下4k型数：
4，8，12，16，„，108；
第三圈:从4开始，删去所有8k-4型数，余下8k型数：
8，16，24，„，104；
第四圈:从8开始，删去所有16k型型数，余下16k-8数：
8，24，40，56，72，88，104；
第五圈:从8开始，删去8，40，72，104，余下 24， 56，88；
第六圈:删去56，余下24，88；再删24，最后留88。
88=54+2+13×2+6，第88号牌为第二副牌中的方块6。
有没有更好的处理方法？
我们发现，当牌数为4张时，最后留下的是4号牌；
当牌数为8张时，最后留下的是8号牌；
当牌数为2
k
张时，最后留下的是2
k
号牌；
现在共有108张牌，取掉44张时，恰好余64张；
按约定先去掉44张牌，第44张是开 始排列中的第87号牌，而第88号牌被
放到余下的64张牌的最后，故最后留下的是第88号牌。
请用此方法计算1，2，„，2004余下的最后的数？
因为2004－1024=980， 所以第980个被去掉的数是第一轮中的1959(980×2
－1) ，第981个被去掉的数是1961，从这儿按规则数最后的数是前面的1960。
从1，2，3，… ，2004中任选k个数，使得所选的k个数中，一定可以找到能构
成三角形边长的3个数(这里要求三 角形三个边长互不相等)。试问：满足条件的
k的最小值。
考虑等价命题：1，2，3，„， 2004中存在
k－
1个数，其中任意3个数均不能
构成一个三角形的3条边长 (这里要求三角形三个边长互不相等)。求满足此条
件的
k
的最大值。
分 析：从小的数开始，找尽量多的数，使之不能构成三角形——两小边之和不大
于第3边：1，2，3，5 ，8，13，21，34，55，89，144，233，377，610，987，
1597， 16 个数！再增加数一定会有两小边之和大于第3边了，所求的
k
的最大
值为17。——怎 样表达？
解：
按条件a
n-2
+ a
n-1
≤a
n
≤2004构造递增的正整数数列{a
n
}，并使得a
n
值最小n
最大：1，2，3，5，8，13，21，34，55，89 ，144，233，377，610，987，1597，
共16个数！其中任意3个数 a
i
、a
j
、a
k
(i＜j＜k

)，总有

a
i
+ a
j
≤a
k-2
+ a
k-1
≤a
k
，两
小数之和大于第3数，不能成为三角形的3条边。
对于任意的、项数不少于17且每项值不超过2004的、递增的正整数数列
{b
n
} ，若存在b
i
、b
j
、b
k
(i＜j＜k ＜17)满足b
i
+ b
j
＞b
k
，则此3个数可以成为三
角形的3边边长；否则，b
k
≥a
k
(k＜17)， b
15
+ b
16
≥

a
15
+ a
16
＞2004≥ b
17
，b
15
，b
16< br>，
b
17
可以成为三角形的3边边长 。即所求的
k
的最小值为17。
例3、在2×3的矩形方格纸上，各个小正方形的顶点称为格点。以格点为顶点

第5页

的等腰直角三角形有（ ）个
A．24 B．38 C．46 D．50
解：
（1）直角边为1的三角形有4×6=24个；
（2）直角边为2的三角形有4×2=8个；
（3）直角边为
2
的三角形有4×2+6=14个； 图5
（4）直角边为
5
的三角形有4个；

1、运用分类计数原理与分步计数原理
分类计数原理与分步计数原理（即加法原理与乘法原理 ）是关于计数的两个
基本原理，是解决竞赛中计数问题的基础。下面提出的三个问题，注意结合排列与组合的相关知识，构造出相应的模型再去分析就可顺利求解。
例4、已知两个实数集合
A

a
1
,a
2
,,a
100
与
B

b
1
,b
2
,,b
50< br>
，若从
A
到
B
的映射
f
使得
B< br>中每个元素都有原象，且
的映射共有（ ）个。
50
f(a
1< br>)≤f(a
2
)≤≤f(a
100
)
49
，则这样
（
A
）
C
100
、 （
B
）
C
99
、 （
C
）
C
100
、 （
D
）
C
99

解：
设
b
1< br>,b
2
,,b
50
按从小到大排列为
c
1
c
2
c
50
（因集合元素具有互异性，
故其中不含相等情形 ）。
将
A
中元素
a
1
,a
2
,,a< br>100
分成50组，每组依次与
B
中元素
c
1
,c< br>2
,,c
50
对
应．这里，我们用
a
1
a
2
a
3
c
1
a
4
a
5
c
2

，表示
f(a
4
)f(a
5
)c
2
f(a
1
)=f(a
2
)=f(a
3
) c
1
48
49
，
，„
，这就是说
c
5 0
只能写考虑
f(a
1
)≤f(a
2
)≤≤f(a
100
)
，容易得到
f(a
100
)c
50
在
a
100
的右边，故只需在
a
1
□a
2
□ a
3
□□a
98
□a
99
□a
100
c
50
之间的99个空位“
□
”
中选择49个位置并按从左到右的顺序 依次填上
c
1
,c
2
,,c
49
。从而构成满足 题
设要求的映射共有
C
99
个。因此选
D
。
例5 、有人要上楼，此人每步能向上走1阶或2阶，如果一层楼有18阶，
他上一层楼有多少种不同的走法？
解法1：
此人上楼最多走18步，最少走9步。这里用
a
18
,a
17
,a
16
,,a
9
分别表示此人
上楼走18 步，17步，16步，„，9步时走法（对于任意前后两者的步数，因后
者少走2步1阶，而多走1步2 阶，计后者少走1步）的计数结果。考虑步子中
的每步2阶情形，易得
a
18
C
18
，
a
17
C
17
，
a
16
C
16
，„，
a
9
C
9
。 0129
C
17
C
16
C
9
1 1712014181
种不同的综上，他上一层楼共有
C
18
走法 。
解法2：
设
F
n
表示上
n
阶的走法的计数结果。
显然，< br>F
1
1
，
F
2
2
（2步1阶；1步2阶 ）。对于
F
3
,F
4
,,
起步只有两种
不同走法 ：上1阶或上2阶。
01
49
29

第6页

因此对于
F
3
，第1步上1阶的情形，还剩
312
阶，计
F
2
种不同的走法；
对于第1步上2阶的情形， 还剩
321
阶，计
F
1
种不同的走法。
总计
F
3
F
2
F
1
213
。
同理 ：
F
4
F
3
F
2
325
，F
5
F
4
F
3
538
，„，
F
18
F
17
F
16
25841597418 1
。
例6、在世界杯足球赛前，
F
国教练为了考察
A,A
12
,…,A
7
这七名队员，准备让
他们在三场训练比赛（每场90分钟）都 上场。假设在比赛的任何时刻，这些队
员中有且仅有一人在场上，并且
A,A,A,A
每人上场的总时间（以分钟为单位）
1234
均被7整除，
A
5
,A
6
,A
7
每人上场的总时间（以分钟为单位）均被13整除。如果
每 场换人次数不限，那么按每名队员上场的总时间计算，共有多少种不同的情况。
解：
设A
i

i1,2,,7

上场的总时间分别为
a< br>i

i1,2,,7

分钟。
根据题意，可设
a
i
7k
i

i1,2,3,4

，
a
i
令

i1
4
13k
i

i5,6,7

，其中
k
i

i1,2,,7

Z

。

7
k
i
m
，

k
i
i5
n
，其中
m≥4
，
n≥3
，且
m,nZ
。则
7m13n270
。
。再

m3313t

m33
易得其一个整数特解为
< br>，又因

7,13

1
，故其整数通解为


n37t

n3
由


3313t≥ 4

37t≥3
，得

29
13
≤t≤0
，故整数
t0,1,2
。
从而其满足条件的所有整数解为

4

m33,

m20,

m7,
。 < br>

n3;

n10;

n17.
对于

k
i
i1
33
的正整数解，可以写一横排共计3 3个1，在每相邻两个1之
4
间共32个空位中任选3个填入“+”号，再把3个“+”号分隔 开的4个部分里
的1分别统计，就可得到其一个正整数解，故

k
i
i1
33
有
C
3
32
个正整数解
7

k
1
,k
2
,k
3
,k
4
；同理

k
i
i5
2
3
有
C2
个正整数解

k
5
,k
6
,k
7< br>
；从而此时满足条件的正整
2
C
2
个。 数解

k
1
,k
2
,k
3
,k
4
,k< br>5
,k
6
,k
7

有
C
3
32
因此满足条件的所有正整数解

k
1
,k
2
, k
3
,k
4
,k
5
,k
6
,k
7

有
C
32
C
2
C
19
C
9
C
6
C
16
49603488424004 2244
323232
个，即按每名队员上场的总时间计
算，共有42244种不同的 情况。
2、运用容斥原理
容斥原理，又称包含排斥原理或逐步淘汰原理。顾名思义，即先计 算一个较
大集合的元素的个数，再把多计算的那一部分去掉。它由英国数学家J.J.西尔
维斯 特首先创立。这个原理有多种表达形式，其中最基本的形式为：
设
A
1
,A
2
,,A
n
是任意
n
个有限集合，则
A
1
∪A
2
∪∪A
n


1≤i≤n
A
i


1≤ij≤n
A
i
∩A
j


1≤ijk≤n
A
i
∩A
j
∩A
k




1

n1
A
1
∩A
2
∩

∩A
n
.

例7、由 数字1，2，3组成
n
位数，且在这个
n
位数中，1，2，3的每一个至少< br>出现一次，问这样的
n
位数有多少个？
解：

第7页

设
U
是由1，2，3组成的
n
位数的集合 ，
A
是
U
中不含数字1的
n
位数的
1
集合 ，
A
是
U
中不含数字2的
n
位数的集合，
A
3
是
U
中不含数字3的
n
位数的
集合，则
2< br>n
U3
；
A
1
A
2
A
32
；
A
1
∩A
2
A
2
∩A
3
A
3
∩A
1
1
；
A
1
∩ A
2
∩A
3
0
。
n
因此
|
n
i1

A
i
|
UA
1
A
2
A
3
A
1
∩A
2
A
2
∩ A
3
A
3
∩A
1
A
1
∩A
2
∩A
3
nnn
3

3323103323
。
nn
即符合题意的
n
位数的个数为
3323
。

下面，我们再来看一个关于容斥原理应用的变异问题。
例8、参加大型团体表演的 学生共240名，他们面对教练站成一行，自左至右按
1，2，3，4，5，„依次报数。教练要求全体 学生牢记各自所报的数，并做下列
动作：先让报的数是3的倍数的全体同学向后转；接着让报的数是5的 倍数的全
体同学向后转；最后让报的数是7的倍数的全体同学向后转。问：
⑴此时还有多少名同学面对教练？
⑵面对教练的同学中，自左至右第66位同学所报的数是几？
解：
⑴ 设
U

1,2,3,,240

，
A
i
表示由< br>U
中所有
i
的倍数组成的集合。则
U240
；

240

A
3


80
3
 
，
240

A
5


48


5


，
240

A
7


34


7


；
。
240

A
15


16


15


，
240

A
21
< br>
11


21


，
240< br>
A
35


6


35


；
240

A
105


2


105


从而此时有
U
< br>A
3
A
5
A
7

2

A
15
A
21
A
35

4A
10 5
136

名同学面对教练。
如果我们借助维恩图进行分析，利用上面所得

③
数据分别填入图6，注意按从内到外的顺序填。
109
55
如图1，此时面对教练的同学一目了然，应有
14 9
2
109+14+4+9=136名。
⑤ 28
4
19 ⑦
⑵用上面类似的方法可算得自左至右第1号至
第105号同学中面对教练的有60名。
考虑所报的数不是3，5，7的倍数的同学没有
图6
转动，他们面对教练；所报的数 是3，5，7中的两
个数的倍数的同学经过两次转动，他们仍面对教练；其余同学转动了一次或三次，< br>都背对教练。
从106开始，考虑是3、5、7的倍数：
3的倍数（由105依次加3）：108，111，114，117，120，„
5的倍数（由105依次加5）：110，115，120，„
7的倍数（由105依次加7）：112，119，„
因此，从106号开始，自左至右，面 对教练的同学所报的数依次是：106，
107，109，113，116，118，120，„
由此可知面对教练的第66位同学所报的数是118。

三、抽屉原则

第8页

10个苹果放入9个抽屉中，无论怎么放，一定有一个抽 屉里放了2个或
更多个苹果。这个简单的事实就是抽屉原则。由德国数学家狄利克雷首先提出来
的。因此，又称为狄利克雷原则。
将苹果换成信、鸽子或鞋，把抽屉换成信筒、鸽笼或鞋盒，这个原则 又叫做
信筒原则、鸽笼原则或鞋盒原则。抽屉原则是离散数学中的一个重要原则，把它
推广到一 般情形就得到下面几种形式：
原则一：把m个元素分成
n
类（m

> n），不论怎么分，至少有一类中有两
个元素。
原则二：把m个元素分成n类
（
m>n
）


< br>（1）当n|m时，至少有一类中含有至少
m
n
m
n
个元素；
]+1个元素
。

m
n
（2）当n|m时，至少有一类中含有至少[
其中n m表示n是m的约数，n m表示n不是m的约数，[
过
m
n
]表示不超
的最大整数。
原则三：把
m
1
m
2
m
2
n1个元素分成n类，则存在一个k，使得
第k类至少有
m
k
个元素。
原则四：把无穷多个元素分成有限类，则至少有一类包含无穷多个元素。
以上这些命题用反证法极易得到证明，这里从略。
一般来说，适合应用抽屉原则解决的数学问 题具有如下特征：新给的元素具
有任意性。如10个苹果放入9个抽屉，可以随意地一个抽屉放几个，也 可以让
抽屉空着。问题的结论是存在性命题，题目中常含有“至少有„„”、“一定
有„„”、 “不少于„„”、“存在„„”、“必然有„„”等词语，其结论只要存在，
不必确定，即不需要知道第 几个抽屉放多少个苹果。
对一个具体的可以应用抽屉原则解决的数学问题还应搞清三个问题：
（1）什么是“苹果”？
（2）什么是“抽屉”？
（3）苹果、抽屉各多少？ < br>用抽屉原则解题的本质是把所要讨论的问题利用抽屉原则缩小范围，使之在
一个特定的小范围内考 虑问题，从而使问题变得简单明确。
用抽屉原则解题的基本思想是根据问题的自身特点和本质，弄清对 哪些元素
进行分类，找出分类的规律。
用抽屉原则解题的基本思想是根据问题的自身特点和本 质，弄清对哪些元素
进行分类，找出分类的规律。
用抽屉原则解题的关键是利用题目中的条件构造出与题设相关的“抽屉”。
例9、在1，4， 7，10，13，„，100中任选出20个数，其中至少有不同的两组
数，其和都等于104，试证明 之。 （第39届美国普特南数学竞赛题）
证明：
给定的数共有34个，其相邻两数的差均为3，我们把这些数分成如下18个
不相交的集合：
{1}，{52}，{4，100}，{7，97}，„{49，55}。
且把它们分作是18个抽屉，从已知的34个数中任取20个数，即把前面两

第9页

个抽屉中的数1和52都取出，则剩下的18个数在后面的16个抽屉中至少 有不
同的两个抽屉中的数全被取出，这两个抽屉中的数互不相同，每个抽屉中的两个
数的和都是 104。
评述：
此例是根据某两个数的和为104来构造抽屉。一般地，与整数集有关的存 在
性问题也可根据不同的需要利用整数间的倍数关系、同余关系来适当分组而构成
抽屉。
例10、设ABC为一等边三角形，E是三边上点的全体. 对于每一个把E分成两个
不相交子 集的划分，问这两个子集中是否至少有一个子集包含着一个直角三角形
的三个顶点？（第24届IMO第 4题）
证明：
如图 7，在边BC、CA、AB上分别取三点P、Q、R，使
P C
BC
3
,QA
CA
3
,RB
AB
3
显然△ARQ，△BPR，△CQP
。
都是直角三角形. 它们的锐角是30°及60°。
设E
1
，E
2
是E的两个非空子集 ，且
EE
1
E
2
,E
1
E
2



由抽屉原则P、Q、R中至少有两点属于同一子集，不妨设
P、Q ∈E
1
。如果BC边上除P之外还有属于E
1
的点，那么结论已明。
设BC的点除P之外全属于E
2
，那么只要AB上有异于B的点S属于E
2
，设S
在BC上的投影点为Ｓ′，则△SS′B为直角三角形。
再设AB内的每一 点均不属于E
2
，即除B之外全属于E
1
，特别，R、A∈E
1，于
是A、Q、R∈E
1
，且AQR为一直角三角形。从而命题得证。
评述：
此例通过分割图形构造抽屉。在一个几何图形内有若干已知点，我们可以根
据 问题的要求把图形进行适当的分割，用这些分割成的图形作为抽屉，再对已知
点进行分类，集中对某一个 或几个抽屉进行讨论，使问题得到解决。
4、割补法的应用
计算几何中的割补法在组合数学 中即表现为计数上的“割补”：欲求解一定
范围内满足条件的元素个数，不妨扩大限定范围求解，例如减 法原理；抑或在统
计中分别求解，再将多余部分删去，例如容斥原理。总之，退一步海阔天空，先
放宽条件，再解决问题就方便多了。
（1）减法原理
这只是一个简单的数学问题而已，可 以看成是加法原理和乘法原理的一个引
申：假设A地到B，C，D地分别有5条路，但到E地只有3条路 ，B，C，D，E
地与F都有3条路相通，于是不妨假设A——E也有5条路相通，于是A——F道路总数为5×4×3=60条，其中有2×3=6条是我们“杜撰”出来的，于是实际上
A——F道 路总数应为60－6=54条。
（2）有禁区的排列问题
我们先介绍有关棋盘多项式的概念。
设C是一个棋盘，R
k
(C)表示把k 个相同的棋子布到C中的方案数。在布棋
时我们规定：当一个棋子放到C中的某个格以后，这个格所在的 行和列就不能
再放其他棋子了，并规定对任意的棋盘C有R
0
(C)=1。
不难得到以下的结果：


第10页

R
1
( )=1，
R
1
()=R
1
（
R
2
()=R
2
（
）=2，
）=0，
R
2
()=1，
可以证明布棋方案数R
k
（C）具有下面的性质：
对于任意的棋盘C和正整数k，如果k大于C中的方格总数，则R（C）=0。
R
1
（C）等于C中的方格数。
设C
1
和C
2< br>是两个棋盘，如果C
1
经过旋转或者翻转变成了C
2
，则R
k
(C
1
)=
R
k
(C
2
)。
设C
i
是从棋盘C中去掉指定的方格所在的行和列以后剩余的棋盘，C
l
是从
棋盘C中去掉指定的方格以后剩余的棋盘，则有R
k
(C)= R
k-1
(C
i
)+ R
k
(C
l
) (k>=1)。
设棋盘C由两个子棋盘C
1
和C
2
组成，如果C< br>1
和C
2
的布棋方案是互相独立
k
的，则有
R
k
(C)

R
i0
i
(C
1
)R
ki
(C
2
)
。
定义1：设C是棋盘，则


R(C)

R
k0
k
(C)x
k

叫做棋盘多项式。
显然，在上述定义中当k大于棋盘的格子数时R
k
（C） =0，所以R（C）一般只
有有限项。例如：R（）=R
0
（）+R
1
（）x+ R
2
（）X
2
=1+2X+X
2

根据R
k
（C）的性质不难得到R（C）的性质。
R（C）=xR(Ci
)+R(C
l
)，其中C
i
和C
l
的定义如 前所述。
R（C）=R(C
i
)×R(C
l
) ，其中C
i
和C
l
的定义如前所述。
利用这两条性质可以计算棋盘多项式。
例11、 计算R（）。
解：
R（）=X*R（）+R（）
=X（1+X）+（1+2X）
=1+3X+X
2

。
下面我们就可以利用棋盘多项式来解决有禁 区的
排列问题。首先可以看到X={1，2，3，……，n}的一
个排列恰好对应了n个棋子在
nn
棋盘上的一种排布。
在图8中，我们以棋盘的n行表示X中的元素，列表示位置，则这种放置方案就对应了排列2143。如果在排列
中限制元素i不能放在第j个位置，则相 应的布棋方案
中的棋盘第
i
行第j列就不能放置棋子。我们把所有这
些不许放 置棋的方格称作禁区。
定理1 设C是
nn
的具有给定禁区的棋盘，这个禁区 图 8
对应集合{1，2，„„，n}中的元素在排列中不允许出现的位置。则这种有禁区
的 排列数是：
n!r
1
(n1)!r
2
(n2)!( 1)r
n

其中
r
i
是i个棋子放置到禁区的方案数。
证明：
n

第11页

先不考虑禁区的限制，那么n 个棋子布到n×n棋盘上的方案有n！·n!个，
如果对n个棋子分别编 号为1，2，„，n，并且认为编号不同的棋子放入同样的
方格是不同的放置方案，那么带编号的棋子布 到n×n棋盘上的方案数是n!·n!。
我们把这些方案构成的集合记作S。
对j=1，2， …，n，令P
j
表示第j个棋子落入禁区的性质，并令A
j
是S中具
图9
1号棋子落入禁区的方案数为R
1
，当它落入禁区的某一格之后，2，3，„，
n号棋子可以任意布置在(n-1) ×(n-1)的棋盘上，由乘法法则得
A
1
R
1
(n1)!(n1)!

同理，对i=2，3，„，n有
A
i
R
1
(n1)!(n1)!
，
对i求和得
n
有性质P
j
的方案构成的子集，那么所求的排列数就 是
A
1
A
2
A
n
。


i1
A
i
R
1
(n1)!n!

1号和2号两个棋子落入禁区的方案数为2R
2
，它们落入以后，3，4，„，n号棋子可以任意布置在（n－2）*（n-2）的棋盘上，所以
A
i

A
j
2R
2
(n2)!(n2)!
，

对所有的
1ijn
求和得


n

2


2


R
2
(n2) !(n2)!
，

R
2
(n2)!n!
A
i

A
j
1ijn
用类似的方法，我们可以求 得


A
i

A
j

A
k
R
3
(n3)!n!
，
1ijn
„„

A
1
A
2
A
n
R
n
n!
。
n
根据容斥原理，带编号的n个棋子都不落入禁区的方案数是
A
1
A
2
A
n
n!n!R
1
(N1)!n! R
2
(n2)!n!(1)R
n
n!
。
需要说明一点，这个定理适用于
nn
棋盘的小禁区的布棋问题。如果是
mn
的棋盘或者是禁区很大的布棋问题，那么只能直接用R（C）来求解。
例12、用四种颜色（红、蓝 、绿、黄）涂染四台仪器A，B，C，D。规定每台仪
器只能用一种颜色并且任意两台仪器都不能相同。 如果B不允许用蓝色和红色，
C不允许用蓝色和绿色，D不允许用绿色－和黄色，问有多少种染色方案？
解：
这个问题就是图中的有禁区的布棋问题。禁区的棋盘多项式为
R（）
16x10x
2
4x
3
,
从而得 到R
1
=6，R
2
=10，R
3
=4，根据定理，所求的方 案数是
N=4！－6*3！+10*2！－4*1！=24－36+20－4=4。

第12页

例13、错位排列问题也可以看作是有禁区的排列问题， 其禁区在主对角线上。
下面使用定理来求D
n
。
解：
禁区的棋盘多项式是
R（





）=R（）* R（）*„„R（）




n个


（1x)
=
2n< br>xxx

=
1


1
 
2

n

，

n
n

n

n

从而得到
R
11
，
R
2



2

< br>，„„，
R
n



n


，代入定理得





n

n

n

D
n
n!n(n1)!

2


(n2)!

(1)
< br>
n


0!



n

n


11

n
1

1

(1)

1!2 !n!


。
总结：
你觉得“数学好玩”吗？只要你有兴趣， 数学就会变得迥然不同。你就会感
受到数学无尽的魅力，就会具有攻无不克的意志力，就会产生无坚不摧 的战斗力。
如果你根本就没爱上数学，又怎么可能碰撞出最为绚烂的火花呢？哪怕非常短
暂，瞬 间即逝。
有很多同学热爱数学，都为能在数学奥林匹克的赛场上一试身手、摘金夺银
而默默钻 研，苦苦奋斗。我想学习中保持长久的数学兴趣和培养创造性的思维是
成功的关键，也是将来可持续发展 的保障。而汲取众家之长是创造性思维的源泉，
学会独立思考是提高创造性思维能力的良策。



第13页