的等腰直角三角形有（ ）个

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??a1,a2,?,a100?与B??b1,b2,?,b50?，若从A到B的映射f使得B中每个元素都有原象，且的映射共有（ ）个。

50f(a1)≤f(a2)≤?≤f(a100)49，则这样

（A）C100、 （B）C99、 （C）C100、 （D）C99 解：

设b1,b2,?,b50按从小到大排列为c1?c2???c50（因集合元素具有互异性，故其中不含相等情形）。

将A中元素a1,a2,?,a100分成50组，每组依次与B中元素c1,c2,?,c50对应．这里，我们用a1a2a3c1a4a5c2?，表示

f(a4)?f(a5)?c2f(a1)=f(a2)=f(a3)?c14849，

，?

，这就是说c50只能写

考虑f(a1)≤f(a2)≤?≤f(a100)，容易得到f(a100)?c50在a100的右边，故只需在a1□a2□a3□?□a98□a99□a100c50之间的99个空位“□”中选择49个位置并按从左到右的顺序依次填上c1,c2,?,c49。从而构成满足题设要求的映射共有C99个。因此选D。

例5、有人要上楼，此人每步能向上走1阶或2阶，如果一层楼有18阶，他上一层楼有多少种不同的走法？ 解法1：

此人上楼最多走18步，最少走9步。这里用a18,a17,a16,?,a9分别表示此人上楼走18步，17步，16步，?，9步时走法（对于任意前后两者的步数，因后者少走2步1阶，而多走1步2阶，计后者少走1步）的计数结果。考虑步子中的每步2阶情形，易得a18?C18，a17?C17，a16?C16，?，a9?C9。

0129?C17?C16???C9?1?17?120???1?4181种不同的综上，他上一层楼共有C18走法。 解法2：

设Fn表示上n阶的走法的计数结果。

显然，F1?1，F2?2（2步1阶；1步2阶）。对于F3,F4,?,起步只有两种不同走法：上1阶或上2阶。

014929 第6页

因此对于

F3，第1步上1阶的情形，还剩3?1?2阶，计F2种不同的走法；

对于第1步上2阶的情形，还剩3?2?1阶，计F1种不同的走法。

总计F3?F2?F1?2?1?3。

同理：F4?F3?F2?3?2?5，F5?F4?F3?5?3?8，?，

F18?F17?F16?2584?1597?4181。

例6、在世界杯足球赛前，F国教练为了考察A,A12,…,A7这七名队员，准备让

他们在三场训练比赛（每场90分钟）都上场。假设在比赛的任何时刻，这些队员中有且仅有一人在场上，并且A,A,A,A每人上场的总时间（以分钟为单位）

1234均被7整除，A5,A6,A7每人上场的总时间（以分钟为单位）均被13整除。如果每场换人次数不限，那么按每名队员上场的总时间计算，共有多少种不同的情况。 解：

设Ai?i?1,2,?,7?上场的总时间分别为ai?i?1,2,?,7?分钟。

根据题意，可设ai?7ki?i?1,2,3,4?，ai令?i?14?13ki?i?5,6,7?，其中ki?i?1,2,?,7??Z?。

?7ki?m，?kii?5?n，其中m≥4，n≥3，且m,n?Z。则7m?13n?270。

。再

?m?33?13t?m?33易得其一个整数特解为?，又因?7,13??1，故其整数通解为??n?3?7t?n?3由??33?13t≥4?3?7t≥3，得?2913≤t≤0，故整数t?0,?1,?2。

从而其满足条件的所有整数解为?4?m?33,?m?20,?m?7,。 ???n?3;?n?10;?n?17.对于?kii?1?33的正整数解，可以写一横排共计33个1，在每相邻两个1之

4间共32个空位中任选3个填入“+”号，再把3个“+”号分隔开的4个部分里的1分别统计，就可得到其一个正整数解，故?kii?1?33有C332个正整数解

7?k1,k2,k3,k4?；同理?kii?52?3有C2个正整数解?k5,k6,k7?；从而此时满足条件的正整

2?C2个。 数解?k1,k2,k3,k4,k5,k6,k7?有C332因此满足条件的所有正整数解?k1,k2,k3,k4,k5,k6,k7?有

C32?C2?C19?C9?C6?C16?4960?34884?2400?42244323232个，即按每名队员上场的总时间计

算，共有42244种不同的情况。

2、运用容斥原理

容斥原理，又称包含排斥原理或逐步淘汰原理。顾名思义，即先计算一个较大集合的元素的个数，再把多计算的那一部分去掉。它由英国数学家J.J.西尔维斯特首先创立。这个原理有多种表达形式，其中最基本的形式为：

设A1,A2,?,An是任意n个有限集合，则

A1∪A2∪?∪An??1≤i≤nAi??1≤i?j≤nAi∩Aj??1≤i?j?k≤nAi∩Aj∩Ak?????1?n?1A1∩A2∩?∩An.

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

第7页

设U是由1，2，3组成的n位数的集合，A是U中不含数字1的n位数的

1集合，A是U中不含数字2的n位数的集合，A3是U中不含数字3的n位数的集合，则

2nU?3；A1?A2?A3?2；A1∩A2?A2∩A3?A3∩A1?1；A1∩A2∩A3?0。

n因此|ni?1?Ai|?U?A1?A2?A3?A1∩A2?A2∩A3?A3∩A1?A1∩A2∩A3nnn3

?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?，Ai表示由U中所有i的倍数组成的集合。则

U?240；

?240?A3????803??，

240?A5???48??5??，

240?A7???34??7??；

。

240?A15???16??15??，

240?A21???11??21??，

240?A35???6??35??；

240?A105???2??105??从而此时有U??A3?A5?A7??2?A15?A21?A35??4A105?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中的两个数的倍数的同学经过两次转动，他们仍面对教练；其余同学转动了一次或三次，都背对教练。

从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）

（1）当n|m时，至少有一类中含有至少

mnmn个元素； ]+1个元素。

mn（2）当n|m时，至少有一类中含有至少[

其中n m表示n是m的约数，n m表示n不是m的约数，[过

mn]表示不超

的最大整数。

原则三：把m1?m2???m2?n?1个元素分成n类，则存在一个k，使得第k类至少有mk个元素。

原则四：把无穷多个元素分成有限类，则至少有一类包含无穷多个元素。 以上这些命题用反证法极易得到证明，这里从略。

一般来说，适合应用抽屉原则解决的数学问题具有如下特征：新给的元素具有任意性。如10个苹果放入9个抽屉，可以随意地一个抽屉放几个，也可以让抽屉空着。问题的结论是存在性命题，题目中常含有“至少有??”、“一定有??”、“不少于??”、“存在??”、“必然有??”等词语，其结论只要存在，不必确定，即不需要知道第几个抽屉放多少个苹果。

对一个具体的可以应用抽屉原则解决的数学问题还应搞清三个问题： （1）什么是“苹果”？ （2）什么是“抽屉”？ （3）苹果、抽屉各多少？

用抽屉原则解题的本质是把所要讨论的问题利用抽屉原则缩小范围，使之在一个特定的小范围内考虑问题，从而使问题变得简单明确。

用抽屉原则解题的基本思想是根据问题的自身特点和本质，弄清对哪些元素进行分类，找出分类的规律。

用抽屉原则解题的基本思想是根据问题的自身特点和本质，弄清对哪些元素进行分类，找出分类的规律。

用抽屉原则解题的关键是利用题目中的条件构造出与题设相关的“抽屉”。 例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，使

PC?BC3,QA?CA3,RB?AB3显然△ARQ，△BPR，△CQP 。都是直角三角形. 它们的锐角是30°及60°。

设E1，E2是E的两个非空子集，且E?E1?E2,E1?E2??

由抽屉原则P、Q、R中至少有两点属于同一子集，不妨设

P、Q∈E1。如果BC边上除P之外还有属于E1的点，那么结论已明。

设BC的点除P之外全属于E2，那么只要AB上有异于B的点S属于E2，设S在BC上的投影点为Ｓ′，则△SS′B为直角三角形。

再设AB内的每一点均不属于E2，即除B之外全属于E1，特别，R、A∈E1，于是A、Q、R∈E1，且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是一个棋盘，Rk(C)表示把k个相同的棋子布到C中的方案数。在布棋时我们规定：当一个棋子放到C中的某个格以后，这个格所在的行和列就不能再放其他棋子了，并规定对任意的棋盘C有R0(C)=1。

不难得到以下的结果：

第10页