第五章 抽屉原理和Ramsey 理论
抽屉原理又称鸽巢原理或重叠原理，是组合数学中两大基本原理之一，是一个极其初等而又应用较广的数学原理。其道理并无深奥之处，且正确性也很明显。但若能灵活运用，便可能得到一些意料不到的结果。
抽屉原理要解决的是存在性问题，即在具体的组合问题中，要计算某些特定问题求解的方案数，其前提就是要知道这些方案的存在性。
1930年英国逻辑学家F. P. Ramsey 将这个简单原理作了深刻推广，即Ramsey 定理，也被称为广义抽屉原理。它是一个重要的组合定理，有许多应用。
5.1 抽屉原理
（一）基本形式
定理5.1.1 （基本形式）将n ＋1个物品放入n 个抽屉，则至少有一个抽屉中的物品数不少于两个。
证 反证之。将抽屉编号为：1,2, …,n ，设第i 个抽屉放有i q 个物品，则 121+=+++n q q q n 但若定理结论不成立，即1≤i q ，即有n q q q +++ 21≤n ，
从而有
n q q q n n ≤+++=+ 211
矛盾。
例 5.1.1 一年365天，今有366人，那么，其中至少有两人在同一天过生日。
注：与概率的区别：抽屉原理讲的是所给出的结论是必然成立的，即100%成立。而概率反映的是不确定性现象发
生的可能性问题，不讨论100%成立的确定性概率问题。 生日悖论：随机选出n 个人，则其中至少有二人同一天出生的概率为
()A P n =n
n
P 365
1365-
特例：()A P 23=50.73%，()A P 100=99.99997%
例 5.1.2 箱子中放有10双手套，从中随意取出11只，则至少有两只是完整配对的。
（二）推广形式
定理5.1.2 （推广形式）将121+-+++n q q q n 个物品放入n 个抽屉，则下列事件至少有一个成立：即第i 个抽屉的物品数不少于i q 个。
（证）反证。不然，设第i 个抽屉的物品数小于i q （i ＝1,2, …,n ）(即该抽屉最多有1-i q 个物品)，则有
11
+-∑=n q n i i ＝物品总数≤()n q q n
i i n i i -=-∑∑==1
1
1
与假设矛盾。
121+-+++n q q q n =
()()()111121
+-++-+-n q q q
（三）特例
推论1 将n(r －1)＋1个物品放入n 个抽屉，则至少有一个抽屉中物品个数不少于r 个。
推论2 将m 个物品放入n 个抽屉，则至少有一个抽屉中物品个数不少于11+??
??
??-n m ＝??
?
???n m
个。其中??x 表示取x
的整数部分，??x 表示不小于x 的最小整数。
推论3 若n 个正整数()n i q i ,2,1=满足
121->+++r n
q q q n
则至少存在一个i q ，满足r q i ≥。
（四）例
例 5.1.3 有 n 位代表参加会议，若每位代表至少认识另外一个代表，则会议上至少有两人认识的人数相同。 (证) 设某代表认识的人数为k 个，则{}1,,2,1-∈n k （视为n －1个抽屉）。而会议上有n 个代表，故每位代表认识的人数共为n 个数（视为n 个物品）。那么，由基本定理，结论成立。
例 5.1.4 任意一群人中，必有两人有相同数目的朋友。 (证) 设有n 个人()2≥n ，分三种情形讨论： (1) 每人都有朋友，由例5.1.3即知结论成立； (2) 只有一人无朋友，余下的n －1人都有朋友，由(1)知此n －1人中必有两人有相同数目的朋友；
(3) 有两人或两人以上的人无朋友，则朋友数为零的人已经有两个了，同样满足条件。
例 5.1.5 边长为2的正方形内有5个点，其中至少有两点，距离不超过2。
(证) 首先制造抽屉：将原正方形各对边中点相连，构成4个边长为1的小正方形（见图5.1.1(a)），视为抽屉。其次，
由基本原理，至少有一个小正方形里点数不少于2。最后，从几何角度可以看出，同一小正方形内的两点的距离不超过小正方形的对角线之长度2，证毕。
图5.1.1 抽屉的选择
注意，如果抽屉选择不当，可能于事无益。如图5.1.1(b)，将正方形分为4个直角边长为2的等腰直角三角形是达不到目的的。
习题1、2
5.2 应用
§5.2.1 抽屉原理的应用
例 5.2.1 任意三个整数，必有两个之和为偶数（其差也为偶数）。 (证) 制造两个抽屉：“奇数”和“偶数”，3
个数放入两个抽屉，必有一个抽屉中至少有两个数，由整数求和的奇、偶性质即知此二数之和必为偶数。 同理可知，二者之差也为偶数。
例 5.2.2 从1,2,…,2n 中任取n ＋1个数，其中至少有一对数，一个是另一个的倍数。
（证）设所取的n ＋1个数为a 1,a 2, …,a n+1，并 （1）表示 ()02≥=i i i r a i αα
，i ＝1,2, …,n ＋1且r i 为奇数。
（2）设置抽屉与物品：1~2n 之间只有n 个奇数（抽屉），故由抽屉原理知此n ＋1个r i 中至少有两个是相同的。设为 r j ＝ r k ＝r ，即r r a j
j
j j α
α
2
2
==，r r a k
k
k k αα2
2
==，
显然有：要么k j a a ，要么j k a a 。
（3）说明：这里已是最好的“可能结果”，即针对各种条件，稍加放松，则结论不一定成立。
● 改为取n 个数，只要取n ＋1,n ＋2, …,2n 这n 个数，显然不满足结论。 ● 改为在1,2,…,2n+1中选n ＋1个数，则结论也不一定成立。例如n=5，选6，7，8，9，10，11
例 5.2.3 设a 1,a 2, …,a m 为任意m 个正整数，则其中必存在若干个相继的数，其和是m 的倍数。即至少存在正整数j 和k(1≤j ＜k ≤m)，使得m 能整除
∑=k
j
i i a =k j j a a a ++++ 1。
(证) 构造数列 ∑==i
j j
i a s 1
=i a a a +++ 21 ，则
s 1
i i s r ≡ mod m ，则0≤r i ＜m （i ＝1,2,…,m ）
若有某 k r ＝0，则k s m ，问题得证。否则，所有i r ≠0，由抽屉原理知，至少存在j m ，从而有∑+== -k j i i j k a s s m 1 。 本题构造“抽屉”与“物品”的技巧在于并不直接针对正整数a i ，而是构造出适合利用抽屉原理的n 个数r i 。为了构造r i ，间接利用了s i 以达到目的。其中的抽屉是取关于模m 的剩余类：0,1, …,m －1，并且在应用抽屉原理时分为两步走。第一步先将r i 分为两大类，即0与非0（或看作两个大抽屉）；第二步，针对非0情形，分为m －1种情况（或看作m －1个小抽屉）。 例 5.2.4 设正整数序列a 1,a 2,…,a 25满足a i+1＋ a i+2＋…＋ a i+5≤6，i ＝0,1,…20。 试证明至少存在正整数j 、k （1≤j ＜k ≤25），使得a j ＋a j+1＋…＋a k ＝19。 (证) 构造序列 ∑==i j j i a s 1 =i a a a +++ 21 ，则 s 1 若有某个s k ＝19，那么，问题得证（j ＝1）。 否则，所有s i ≠19。 令集合 A ＝{ s 1，s 2，…，s 25，s 1＋19，s 2＋19，…，s 25＋19} 且有 20≤s 1＋19＜s 2＋19＜…＜s 25＋19≤49。 集合A 中共有50个数，每个数的取值在1到49之间，由抽屉原理，其中必有两数相同。又知i ≠j 时，s i ≠s j ，从而 s i ＋19≠s j ＋19 。 所以，相等的两项必为 s k ＝ s j ＋19（显然k>j ）， 即 ∑+== -=k j i i j k a s s 1 19=k j j a a a +++++ 21 ，证毕。 问题一般化：设正整数序列a 1,a 2,…,a mn 满足a i+1＋ a i+2＋…＋ a i+n ≤p ，i ＝0,1,…,n(m －1)。 若要求存在正整数j 分析：令 s i ＝a 1＋a 2＋…＋a i ， i ＝0,1,…,nm 设 A ＝{ s 1，s 2，…, s mn ，s 1＋q ，s 2＋q , …，s mn ＋q } 且有 1≤s 1< s 2< …< s mn ， q< s 1＋q< s 2＋q <… 要用抽屉原理，A 中元素个数必须大于A 中最大数s mn ＋q ，即mp ＋q<2mn ，或12-≤+mn q mp ，由此得结论：q ≤m(2n －p)－1 。 本例中，m ＝n ＝5，p ＝6，q ＝19 。 若选m ＝n ＝10，p ＝16，则q ≤39 。 变异：一学生用37天共60小时复习功课，第i 天复习a i 小时（a i 为正整数），则无论如何安排，总存在相继若干天，这些天的复习时数之和恰为13 。 此问题实际上隐含着m ＝1，n ＝37，p ＝60，q ＝13 。 这时，问题可以描述为：m 个正整数a 1,a 2,…,a m 满足 a 1＋a 2＋…＋a m ＝n ，要存在m k j 1≤<≤，使得a j ＋ a j+1＋…＋ a k ＝q ，必须有q ≤2m －n －1（这只要在一般问题中取m ＝1，n ＝m ，p ＝n 即可）。 例 5.2.5 将65个正整数1,2, …,65随意分为4组，那么，至少有一组，该组中最少存在一个数，是同组中某两数之和或另一数的两倍。 (证) 用反证法。设任何一组数中的每一个数，它既不等于同组中另外两数之和，也不等于同组中另一数的两倍。即任何一组数中的的任意两个数之差总不在这个组中。 由抽屉原理，四组中至少有一组（称为A 组），其中至少有17个数。从中取17个：记为a 1,a 2,…,a 17，不妨设a 17最大。令 () i i a a a -=171， i ＝1,2, …,16 显然()6511<≤i a 。 由假设知()A a i ?1（否则，就有某个a k 和a k 满足a 17=a k +a j ），所以，该16个数必在另外三组B 、C 、D 中。 再由抽屉原理知，B 、C 、D 三组中至少有一组（设为B 组），至少含有6个() 1i a 。只取其中6个，记为b 1,b 2,…,b 6， 同理可设b 6最大，并令() i i b b b -=61（i ＝1,2,…,5）。同样有 () 6511<≤i b 且() B b i ?1。而且由假设知 () () ()A a a a a a a b b b j k k j i i ?-=---=-=171761 （k j a a <） 故该5个数一定在C 或D 中。 又由抽屉原理，设C 组中至少有3个()1i b ，取其中3个记为321c c c << 。 同理可证132231,c c d c c d -=-=（21d d <，651<≤i d ）也不在A 、B 、C 三组中，故必在D 组中。进一步，可证得1212c c d d e -=-=不在A 、B 、C 、D 中，且满足651<≤e 。 这说明从1到65的这65 个整数中有一个不在A 、B 、C 、D 这4组的任何一组中，与题设矛盾。 例 5.2.6 由mn ＋1个不同实数构成的序列{}1,2,1+=mn i a i 中必存在一个(m ＋1)项的递增子序列或(n ＋1)项的递减子序列。 (证) 某个序列{}n n b n ,2,1=是递增的，是指该序列满足：n b b b <<< 21；反之，若n b b b >>> 21，则称其是递减的。 针对每一个a i ，以a i 为首项，向后寻找递增子序列，最长子序列的项数（即长度）记为t （i ＝1,2, …,mn ＋1），则1≤i t ≤mn ＋1 (若a i 之后每一项都比a i 小，则i t ＝1；若a i 之后有一项a j 比a i 大，则i t ＝2；若a j 之后还有一项a k 比a j 大，则i t ＝3 …)。 例如，对m=2，n=4序列 4 5 2 9 3 1 8 6 7 1t =4，2t =3，3t =4，4t =1，5t =3，6t =3，7t =1，8t =2，9t =1 若有某个 i t ≥m ＋1，则问题得证。 否则，所有 1≤i t ≤m ，由推论1，至少有n ＋1个i t 相等，设 1 2 1 +===n k k k t t t ， 且11121+≤<<<≤+mn k k k n 那么，必有121+>>>n k k k a a a ，从而构成n ＋1个实数的递减子序列。事实上，若j i k k <时，有j i k k a a <，则以i k a 为首项的最长子序列比以j k a 为首项的最长子序列多一项，即j i k k t t <，矛盾。 本例已达到最好的可能结果。 特例：m ＝n 。 实际的问题为：不同高度的12+n 个人 随意排成一行，那么总能从中挑出n ＋1个人，让其出列后，他们恰好是由低向高（或由高向低）排列的。 例 5.2.7 证明：对任意正整数n ，必存在由仅由数字0、3和7组成的正整数，该正整数能被n 整除。 （证）证法一：仿照上例，构造 200037个t t a =()()1,,2,1,0-=n n t ， 令 n a r t t m od ≡， ()()1,,2,1,0-=n n t 其中t r 取最小非负剩余，即n r t <≤0。则由抽屉原理，至 少有n 个t r 相同。设其为j i r ()n j ,,2,1 =，那么，由同余 运算的性质知，n 能整除 a ＝∑=n j i j a 1 。而a 恰好仅由0、3、 7构成。 证法二：构造 " 37"2373737对t t a = ()n t ,,2,1 =，令 n a r t t m od ≡， ()n t ,,2,1 = t r 同样取最小非负剩余。 （1） 若有某个k r ＝0，那么，n 必能整除k a ，结论成立。 （2） 否则，所有t r ≠0，即11-≤≤n r t ()n t ,,2,1 =。 由抽屉原理的简单形式，必有某两个t r 相等。不失一般性，可设k j r r =且k j <，由同余运算的性质知 n a a k j mod ≡ 即n 能整除j k a a -，而 j k a a -＝ " 37"000373737对对j j k - 仅由0、3、7构成。 例 5.2.8 已知402个集合,每个集合都恰有20个元素，其中每两个集合都恰有一个公共元素。求这402个集合的并集所含元素的个数。 （解）设所给的402个集合为X A A A ,,,,40121 ，又设{} 2021,,,x x x X =。由条件知1=j XA ()401,,2,1 =j ，即每个j A ()401,,2,1 =j 中恰 好含有X 中的某一个元素i x ()20,,3,2,1 =i 。记诸j A 中包含i x 的集合的个数为i q ()20,,3,2,1 =i ，则 2021q q q +++ ＝∑=401 1 j j XA ＝∑=401 1 1j ＝401＝20×20＋1 由抽屉原理，必有正整数()4011≤≤k k ，使得21≥k q 。下面证明此401=k q 且其余的诸0=i q ()k i i ≠=；20,,3,2,1 。 如果401≠k q ，即401 t A ()4011≤≤t ，满足{}r t x XA =，从而由1=t XA 知 t k A x ?。 （例如k=1，q 1=21，q 2>0，t=22，r=2） 设包含k x 的k q 个集合是k q B B B ,,,21 （例如B i =A i ，i=1,2,…,21），则同样由条件知()k t i q i A B ,,2,11 ==。所以可设{}i t i b A B = ()k q i ,,2,1 =，并知k q b b b ,,21彼此相异（否则若有某两个s r b b =()k q r s ≤<≤1，则必有{}2,,≥= r k s r b x B B ，矛盾）。这说明 {} ,,,,21k q t b b b A =，从而有2021>≥≥k t q A ，这又 与题设20=t A 矛盾，所以必有401=k q 。从而知()401,,2,1 =∈i A x i k 。 令{}k i i x A C -=()401,,2,1 =i ，{}k x X C -=402，则19=i C ，且有Φ=j i C C ()4021≤<≤j i ，于是 402 1 401 1 1==+ =+ i i i i C A X ＝1＋∑=402 1 i i C ＝1＋19×402＝7639 例 5.2.9 将上下两个同心而且同样大小的圆盘A ，B 分别划分成200个全等的扇形，在A 盘上任取100个扇形涂上红色，其余100个扇形涂上蓝色，而B 盘上的200个扇形任意地涂上红色或蓝色。证明，总可适当地转动两圆盘到某个位置，当上下的扇形互相重合时，两圆盘上至少有100对具有相同颜色的扇形重迭在一起。 （证）定义两圆盘的扇形对齐时为一种重迭格局，由于每个圆盘都分为200个扇形，故当其中一个圆盘转动时，可能出现的重迭格局有200个。对这200个格局计算同色扇形重迭的对数。由于A 盘上红、蓝扇形各100个，因此，B 盘上每个扇形（或红色或蓝色）在这200个格局里与A 盘上的同色扇形各重迭100次。对B 盘的每个扇形统计，在这200个格局中B 盘的200个扇形与A 盘同色扇形重迭在一起共100×200＝20000对。因此可计算出每一格局中同色扇形重迭的平均对数为20000÷200=100。因此至少有一格局中同色扇形重迭的至少有100对。 例 5.2.10 某俱乐部有3n+1名成员。对每一个人，其余的人中恰好有n 个愿与他打网球，n 个愿与他下象棋，n 个愿与他打乒乓，证明该俱乐部至少有3个人，他们之间玩的游戏三种俱全。 （证）将每个人作为平面上的一个点，且任何3点不共线。由每一点引出n 条红边，n 条蓝边，n 条黑边，分别代表打网球，下象棋及打乒乓。问题等价于要证明图中至少 有一个三边颜色全不相同的三角形。 考虑由这3n ＋1个点的所有连边构成的异色角（即两条异色的边所构成的角）的总数L 。 每个顶点处有个3n 2异色角，所以 L ＝()1332+n n 平均每个三角形有 () 21 3613331 32 >-= ++n n C n n n 个异色角。因此，至少有一个三角形有3个异色角，那么，这个三角形的三条边当然互不同色。 本题也可以从同色角的总个数入手，两种解法并无实质上的差别。 §5.2.2 极端原理 定理5.2.1极端原理： 最小数原理1 在有限个实数组成的集合中，必存在最小的数。 最小数原理2 设N 是自然数全体组成的集合，若M 是N 的非空子集，则M 中必有最小的数。 最大数原理1 在有限个实数组成的集合中，必存在最大的数。 最大数原理2 在由负整数组成的集合（有限或无限）中必存在最大的负整数。 最短长度原理1 任意给定相异两点，所有连接这两点的线中，以直线段的长度为最短。 最短长度原理2 在连接一个已知点与某个已知直线或已知平面上的点的所有线段中，以垂线段的长度为最短。 【例5.2.11】某次体育比赛，每两名选手赛一场，每 场比赛一定决出胜负。通过比赛确定优秀选手。选手A 为优秀选手的条件是：对任何选手B ，或者A 胜B ，或者A 间接胜B 。所谓间接胜B 是指存在选手C ，使得A 胜C 而C 胜B 。如果按上述规则确定的优秀选手只有一名。求证这名选手全胜所有其他选手。 证 先证优秀选手的存在性。因参赛选手有限，故由极端原理之最大数原理知，必存在胜场次数最多的选手。设A 是胜场次数最多的选手之一。若A 胜所有其他选手，当然是优秀选手。若不然，设A 胜1B ，k B B ,,2 ，而负于 n B B k ,,1 +。任取j B （n j k ≤≤+1），则他不能全胜1B ，k B B ,,2 ，否则j B 会比A 至少多胜一场，矛盾。因此必存 在i B （k i ≤≤1），使A 胜i B ，i B 胜j B ，即A 间接胜j B 。由j B 的任意性，即知A 为优秀选手。 再证：若优秀选手惟一，则他必全胜所有其他选手。 设A 是惟一优秀选手。若A 不全胜所有其他选手，设A 胜1B ，k B B ,,2 而负于n B B k ,,1 +，n k <。由前述证明知n B B k ,,1 +又存在局部优秀选手j B 。对任何i B （k i ≤≤1），都有j B 胜A ，A 胜i B ，即j B 间接胜i B ，从而j B 也是优秀选手，矛盾。所以这样的j B 不存在，从而A 必全胜所有其他选手。 【例 5.2.12】已知n a a a ,,,21 与n b b b ,,,21 是n 2个 正数，且122221=+++n a a a ，122221=+++n b b b ，求 证：n n b a b a b a , ,,2211 中存在一个值一定不大于1。 证 因为n n b a b a b a , ,,2211 这n 个数中，必有最小数，不妨设为 r r b a ，即 i i r r b a b a ≤ （i=1,2,…,n ）。由于0>i b ，于是 i i r r a b b a ≤，即2 22 i i r r a b b a ≤??? ? ?? ， i=1,2,…,n 因此 () 2 2221 2 n r r b b b b a +++??? ? ?? ≤2 2221n a a a +++ 由题设条件即有2 ???? ??r r b a ≤1，亦即r r b a ≤1。 若将条件n a a a ,,,21 与n b b b ,,,21 是2n 个正数改为 2n 个实数，且122221=+++n a a a ，12 2221=+++n b b b ， 则结论变为 1 1b a ， 2 2b a ，…， n n b a 中存在一个值一定不大于1。 5.3 R a m s e y 问题 Ramsey 理论起始于二十世纪20年代末、30年代初，最初由英国数学家F.P.Ramsey 提出。其思想已日益被人们理解、接受并得到了一定的发展。 Ramsey 定理是抽屉原理的推广，也叫广义抽屉原理。 §5.3.1 完全图的染色问题 （一）完全图 设平面上有n 个点，任何三点都不共线，将这些点两两 之间连一线段，构成的图形称为完全图，记为n K 。 （二）问题 问题一、证明任意6个人的集会上，总有3人互相认识或互相不认识（1947年匈牙利数学竞赛试题，后被收入1958年的“美国数学月刊”第5、6期中）。 问题二、1959年，“美国数学月刊”又进一步提出：“任意18个人的集会上，一定有4人或互相认识，或互不认识”。 （三）问题的转化 将6个人视为平面上的6个点（无3点共线），过这些顶点作完全图6K ，其中要求互相认识的二人用红色线段相连，否则连以蓝色线段。 问题一：将6K 的边涂以红、蓝两色，则一定会出现一个同色的三角形。 §5.3.2 R a m s e y 问题 提法一、经观察，在6个或6个以上的人群中，必有3人互相认识，或有3人，彼此根本不认识。而将人数降到5个或更少时，此有趣现象就可能消失。于是6成为具有这一特性的最少人数。 提法二、将平面上无3点共线的n 个顶点任意两点之间都连上且仅连上一条边，就得到一个n 个顶点的完全图，记为n K 。 当n ≥6时，若对n K 的每一条边随意涂以红、 蓝两色之一。那么，n K 上至少可以找出一个同色3K 。 而当n ≤5时，至少可以给出一种涂法，使得n K 上不存在同色3K （见图5.3.1，其中实线表示蓝线，虚线表示红线）。 图5.3.1 无同色3K 的五边形染色方案 提法三、设集合{}n e e e A ,,,21 =，令 {}2, =?=X A X X S （即A 上所有二元子集类） ，再用{}21,S S 表示S 的一个二分拆（即S S S =+21，=21S S φ，i S 可空）。那么，当n ≥6时，对集合A 中的元素，下面结论至少有一个成立： （1） 存在3个元素，其全部二元子集都属于1S ； （2） 存在3个元素，其全部二元子集都属于2S 。 而当n ≤5时，结论未必成立。 三种提法各有利弊，提法一比较直观，二便于分析，三有利于理论推广。 证明、在6K 中任选一顶点1v ，由抽屉原理，以1v 为端 点的5条边至少有3条是同色的。不妨设边21v v 、31v v 、41v v 都为红色，现考察连接2v 、3v 、4v 的3条边，若这3条边全为蓝色，则△2v 3v 4v 就是一个蓝色三角形。否则，3条边中至少有一个为红色（假设为2v 3v ），则△1v 2v 3v 就是一个 红色三角形。命题得证。 §5.3.3 问题的一般化 将顶点数扩大：例如，用红蓝两色对9K 的边着色，则必出现同色的3K 或同色4K ，但对8K 着色则不能保证有上述结果； 对14K 而言，存在同色的3K 或5K ； 对18K 的边涂以红蓝两色，则存在同色的4K ，那么，对17K ，能否存在同色4K 呢？ 引理 若将9K 涂以红蓝两色，则必存在一个顶点，从此点引出的8条线段中，同色的线段或多于3条，或少于3条。 (证明) 用反证法。假如不存在这样的顶点，即从每一顶点发出的线段中，红色（蓝色）线段都是3条，现在对9个顶点逐点统计由它们发出的红色（蓝色）线段的条数，应为27。另一方面，设9 K 中实有红色（蓝色）线段共m 条，现在对这m 条边的每个端点逐点统计由它们发出的红色（蓝色）线段的条数，由于每条线段有两个端点，故应为2m 。 于是得出2m ＝27，这是不可能的。引理得证。 定理5.3.1. 对9K 涂以红蓝两色，必定会出现一个同色的3K 或同色4 K 。 (证) 设9K 的顶点为0v ，1v ，…，8v ，不失一般性，设0v 为满足引理条件的一点。现分两种情况讨论如下： （1）从0v 引出的8条线段中，红色线段多于3条，即至少有4条，不妨设为10v v 、20v v 、30v v 、40v v ，再看由1v ，2v ，3v ，4v 这4个顶点构成的K 4，若其中至少有一条红边，则它的两个端点与0v 便构成一个红色的K 3，否则，该K 4的所有边全为蓝色，即存在同色K 4。 （2）若红色线段少于3条，那么，从0v 引出的蓝色线段至少有6条，不妨设为10v v 、20v v 、30v v 、40v v 、50v v 、60v v 。 再看1v ，2v ，3v ，4v ，5v ，6v 这6个顶点构成的K 6，由前述结论，K 6中必有一个同K 3，若是红色的，则结论已真；若为蓝色，则该K 3的三个顶点与0v 一起便构成一个蓝色K 4 ，结论亦真。 综合以上两种情况，定理5.3.1得证。 当n ＝8时，可以给出一种涂法，使得染色后的K 8中既无红色K 3，又无蓝色K 4（见图5.3.2 ）。 图5.3.2 既无红色3K 又无蓝色4 K 的八边形染色方案 （实线——红色，虚线——蓝色） 注：但存在蓝色的3K 。 习题二证明：在一个至少有2人的小组中，总存在两个人，他们在组内所认识的人数相同。证明：假设没有人谁都不认识：那么每个人认识的人数都为[1,n-1]，由鸽巢原理知，n个人认识的人数有n-1种，那么至少有2个人认识的人数相同。假设有1人谁都不认识：那么其他n-1人认识的人数都为[1,n-2]，由鸽巢原理知，n-1个人认识的人数有n-2种，那么至少有2个人认识的人数相同。假设至少有两人谁都不认识，则认识的人数为0的至少有两人。 任取11个整数，求证其中至少有两个数的差是10的整数倍。证明：对于任意的一个整数，它除以10的余数只能有10种情况：0，1，…，9。现在有11个整数，由鸽巢原理知，至少有2个整数的余数相同，则这两个整数的差必是10的整数倍。证明：平面上任取5个坐标为整数的点，则其中至少有两个点，由它们所连线段的中点的坐标也是整数。证明：有5个坐标，每个坐标只有4种可能的情况：（奇数，偶数）；（奇数，奇数）；（偶数，偶数）；（偶数，奇数）。由鸽巢原理知，至少有2个坐标的情况相同。又要想使中点的坐标也是整数，则其两点连线的坐标之和为偶数。因为奇数+奇数= 偶数；偶数+偶数=偶数。因此只需找以上2个情况相同的点。而已证明：存在至少2个坐标的情况相同。证明成立。 一次选秀活动，每个人表演后可能得到的结果分别为“通过”、“淘汰”和“待定”，至少有多少人参加才能保证必有100个人得到相同的结果证明：根据推论2.2.1，若将3*（100-1）+1=298个人得到3种结果，必有100人得到相同结果。一个袋子里装了100个苹果、100个香蕉、100个橘子和100个梨。那么至少取出多少水果后能够保证已经拿出20个相同种类的水果证明：根据推论2.2.1，若将4*（20-1）+ 1 = 77个水果取出，必有20个相同种类的水果。 填空题 1．将 5 封信投入 3 个邮筒，有 _____243_种不同的投法． 2． 5 个男孩和 4 个女孩站成一排。如果没有两个女孩相邻，有43200方法． 3． 22 件产品中有 2 件次品，任取 3 件，恰有一件次品方式数为__ 380 ______． 4．( x y)6所有项的系数和是_64_ _．答案：645．不定方程 x1x2x3 2 的非负整数解的个数为 _ 6 ___． 6 ．由初始条件 f (0)1, f (1) 1 及递推关系 f ( n2) f (n1) f ( n) 确定的数列{ f (n)} ( n0) 叫做Fibonacci数列 10 7．（ 3x-2y ）20的展开式中 x10y10的系数是c20310( 2)10． 8．求 6 的 4 拆分数P4(6)2． 9．已知在Fibonacci数列中，已知 f (3)3,f (4)5, f (5) 8 ，试求Fibonacci 数f (20)10946 10 ．计算P4(12) 4 P4 (12)P k (12)P1 (8)P2 (8)P3 (8)P4 (8) k1 34 P1 (8) P2 (8)P k (5)P k (4)14 5 515 k1k 1 11．P4(9)（ D） A． 5 B. 8 C. 10 D. 6 12．选择题 1．集合 A{ a1 , a 2 ,L , a10 } 的非空真子集的个数为（A） C. 1024 2．把某英语兴趣班分为两个小组，甲组有 2 名男同学， 5 名女同学；乙组有 3 名男同学， 6名女同学，从甲乙两组均选出 3 名同学来比赛，则选出的 6 人中恰有 1 名男同学的方式数是（ D ） A． 800 B. 780 C. 900 D.850 3．设( x , y) 满足条件x y10 ，则有序正整数对( x, y) 的个数为（D） A. 100 C. 50 4．求( x03x12x2x3 )6中 x02 x13 x2项的系数是（C） B. 60 5．多项式(2 x0x14x2x3 )4中项 x02x12x2的系数是（C） A． 78 B. 104 C. 96 D. 48 6．有 4 个相同的红球， 5 个相同的白球，那么这9 个球有（ B）种不同的排列方式 A. 63 B. 126 C. 252 7．递推关系 f (n ) 4 f ( n1) 4 f (n 2) 的特种方程有重根2，则（ B ）是它的一般解 A．c12n 1c2 2n B.(c1c2n)2 n C.c(1n)2 n D.c1 2n c2 2n 8．用数字 1,2,3,4（数字可重复使用）可组成多少个含奇数个1、偶数个 2 且至少含有一个 3 的n (n1) 位数（）运用指数生产定理 A. 4n 3n ( 1)n B.4n3n14n2n 1 .4n3n( 1)n 4433 抽屉原理公式及例题“至少……才能保证(一定)…最不利原则 抽屉原则一：如果把(n+1)个物体放在n个抽屉里，那么必有一个抽屉中至少放有2个物体。例：把4个物体放在3个抽屉里，也就是把4分解成三个整数的和，那么就有以下四种情况：抽屉原则二：如果把n个物体放在m个抽屉里，其中n>m，那么必有一个抽屉至少有： ①k=[n/m ]+1个物体：当n不能被m整除时。 ②k=n/m个物体：当n能被m整除时。 例1．木箱里装有红色球3个、黄色球5个、蓝色球7个，若蒙眼去摸，为保证取出的球中有两个球的颜色相同，则最少要取出多少个球？ 解：把3种颜色看作3个抽屉，若要符合题意，则小球的数目必须大于3，故至少取出4个小球才能符合要求。 例2．一幅扑克牌有54张，最少要抽取几张牌，方能保证其中至少有2张牌有相同的点数？解：点数为1(A)、2、3、4、5、6、7、8、9、10、11(J)、12(Q)、13(K)的牌各取1张，再取大王、小王各1张，一共15张，这15张牌中，没有两张的点数相同。这样，如果任意再取1张的话，它的点数必为1～13中的一个，于是有2张点数相同。15+1=16 例3：从一副完整的扑克牌中，至少抽出（）张牌，才能保证至少6张牌的花色相同？A.21 B.22 C.23 D.24 解：完整的扑克牌有54张，看成54个“苹果”，抽屉就是6个（黑桃、红桃、梅花、方块、大王、小王），为保证有6张花色一样，我们假设现在前4个“抽屉”里各放了5张，后两个“抽屉”里各放了1张，这时候再任意抽取1张牌，那么前4个“抽屉”里必然有1 个“抽屉”里有6张花色一样。答案选C. 例4：2013年国考：某单位组织4项培训A、B、C、D，要求每人参加且只参加两项，无论如何安排，都有5人参加培训完全相同，问该单位有多少人？ 每人一共有6种参加方法（4个里面选2个）相当于6个抽屉，最差情况6种情况都有4个人选了，所以4*6=1=25 例5：有300名求职者参加高端人才专场招聘会，其中软件设计类、市场营销类、财务管理类和人力资源管理类分别有100、80、70和50人。问至少有多少人找到工作，才能保证一定有70名找到工作的人专业相同? 用最不利原则解题。四个专业相当于4个抽屉，该题要有70名找到工作的人专业相同，那最倒霉的情况是每个专业只有69个人找到工作，值得注意的是人力专业一共才50个人，因此软件、市场、财务各有69个人找到工作，人力50个人找到工作才是本题中最不利的情形，最后再加1，就必定使得某专业有70个人找到工作。即答案为69×3+50+1=258。 例6：调研人员在一次市场调查活动中收回了435份调查问卷，其中80%的调查问卷上填写了被调查者的手机号码。那么调研人员需要从这些调查问卷中随机抽多少份，才能保证一定能找到两个手机号码后两位相同的被调查者？ 答:在435份调查问卷中，没有填写手机号码的为435×(1-80%)=87份。要找到两个手机号码后两位相同的被调查者，首先要确定手机号码后两位有几种不同的排列方式。因为每一位 作业习题答案 习题二 2.1证明：在一个至少有2人的小组中，总存在两个人，他们在组内所认识的人数相同。 证明： 假设没有人谁都不认识：那么每个人认识的人数都为[1,n-1]，由鸽巢原理知，n 个人认识的人数有n-1种，那么至少有2个人认识的人数相同。 假设有1人谁都不认识：那么其他n-1人认识的人数都为[1,n-2]，由鸽巢原理知，n-1个人认识的人数有n-2种，那么至少有2个人认识的人数相同。 2.3证明：平面上任取5个坐标为整数的点，则其中至少有两个点，由它们所连线段的中点的坐标也是整数。 证明： 方法一： 有5个坐标，每个坐标只有4种可能的情况：（奇数，偶数）；（奇数，奇数）；（偶数，偶数）；（偶数，奇数）。由鸽巢原理知，至少有2个坐标的情况相同。又要想使中点的坐标也是整数，则其两点连线的坐标之和为偶数。因为 奇数+奇数 = 偶数 ； 偶数+偶数=偶数。因此只需找以上2个情况相同的点。而已证明：存在至少2个坐标的情况相同。证明成立。 方法二： 对于平面上的任意整数坐标的点而言，其坐标值对2取模后的可能取值只有4种情况，即：(0,0) ,(0,1) ,(1,0), (1,1)，根据鸽巢原理5个点中必有2个点的坐标对2取模后是相同类型的，那么这两点的连线中点也必为整数。 2.4一次选秀活动，每个人表演后可能得到的结果分别为“通过”、“淘汰”和“待定”，至少有多少人参加才能保证必有100个人得到相同的结果？ 证明： 根据推论2.2.1，若将3*（100-1）+1=298个人得到3种结果，必有100人得到相同结果。 2.9将一个矩形分成(m +1)行112m m +?? + ??? 列的网格每个格子涂1种颜色，有m 种颜色可以选择，证明：无论怎么涂色，其中必有一个由格子构成的矩形的4个角上的格子被涂上同一种颜色。 证明： （1）对每一列而言，有（m+1）行，m 种颜色，有鸽巢原理，则必有两个单元格颜色相同。 （2）每列中两个单元格的不同位置组合有12m +?? ??? 种，这样一列中两个同色单元格的位置组合共有 12m m +?? ??? 种情况 （3）现在有112m m +?? + ??? 列，根据鸽巢原理，必有两列相同。证明结论成立。 2.11证明：从S={1,3,5,…,599}这300个奇数中任意选取101个数，在所选出的数中一定存在2个数，它们之间最多差4。 证明： 高中数学竞赛标准讲义----排列组合与概率 一、基础知识 1．加法原理：做一件事有n 类办法，在第1类办法中有m 1种不同的方法，在第2类办法中有m 2种不同的方法，……，在第n 类办法中有m n 种不同的方法，那么完成这件事一共有N=m 1+m 2+…+m n 种不同的方法。 2．乘法原理：做一件事，完成它需要分n 个步骤，第1步有m 1种不同的方法，第2步有m 2种不同的方法，……，第n 步有m n 种不同的方法，那么完成这件事共有N=m 1×m 2×…×m n 种不同的方法。 3．排列与排列数：从n 个不同元素中，任取m(m ≤n)个元素，按照一定顺序排成一列，叫做从n 个不同元素中取出m 个元素的一个排列，从n 个不同元素中取出m 个(m ≤n)元素的所有排列个数，叫做从n 个不同元素中取出m 个元素的排列数，用m n A 表示，m n A =n(n-1)…(n-m+1)= )! (! m n n -,其中m,n ∈N,m ≤n, 注：一般地0n A =1，0！=1，n n A =n!。 4．N 个不同元素的圆周排列数为n A n n =(n-1)!。 5．组合与组合数：一般地，从n 个不同元素中，任取m(m ≤n)个元素并成一组，叫做从n 个不同元素中取出m 个元素的一个组合，即从n 个不同元素中不计顺序地取出m 个构成原集合的一个子集。从n 个不同元素中取出m(m ≤n)个元素的所有组合的个数，叫做从n 个不同元素中取出m 个元素的组合数，用m n C 表示： .)! (!! !)1()1(m n m n m m n n n C m n -=+--= 6．组合数的基本性质：（1）m n n m n C C -=；（2）11--+=n n m n m n C C C ；（3）k n k n C C k n =--11；（4）n n k k n n n n n C C C C 20 10==+++∑= ；（5）111++++-=+++k m k k m k k k k k C C C C ；（6）k n m n m k k n C C C --=。 7．定理1：不定方程x 1+x 2+…+x n =r 的正整数解的个数为11--n r C 。 [证明]将r 个相同的小球装入n 个不同的盒子的装法构成的集合为A ，不定方程x 1+x 2+…+x n =r 的正整数解构成的集合为B ，A 的每个装法对应B 的唯一一个解，因而构成映射，不同的装法对应的解也不同，因此为单射。反之B 中每一个解(x 1,x 2,…,x n ),将x i 作为第i 个盒子中球的个数，i=1,2,…,n ，便得到A 的一个装法，因此为满射，所以是一一映射，将r 个小球从左到右排成一列，每种装法相当于从r-1个空格中选n-1个，将球分n 份，共有11--n r C 种。故定理得证。 推论1 不定方程x 1+x 2+…+x n =r 的非负整数解的个数为.1r r n C -+ 抽屉原理的经典解题思路 抽屉原理在公务员考试中的数字运算部分时有出现。抽屉原理是用最朴素的思想解决组合数学问题的一个范例，我们可以从日常工作中的实例来体会抽屉原理的应用。抽屉原理的内容简明朴素，易于接受，它在数学问题中有重要的作用。许多有关存在性的证明都可用它来解决。 先来看抽屉原理的一般叙述： 抽屉原理（1）：讲多于n件的物品任意放到n个抽屉中，那么至少有一个抽屉中的物品的件数不少于2。抽屉原理（1）可以进行推广，把无穷多个元素放入有限个集合里，则一定有一个集合里含有无穷多个元素。 抽屉原理（2）：将多于件的物品任意放到抽屉中，那么至少有一个抽屉中的物品的件数不少m+1。也可以表述成如下语句：把m个物品任意放入n（n≤m）个抽屉中，则一定有一个抽屉中至多要有k件物品。其中k＝〔m/n 〕，这里〔m/n 〕表示不大于m/n的最大整数，即m/n的整数部分。 掌握了抽屉原理解题的步骤就能思路清晰的对一些存在性问题、最小数目问题做出快速准确的解答。一般来讲，首先得分析题意，分清什么是“物品”，什么是“抽屉”，也就是什么作“物品”，什么可作“抽屉”。接着制造抽屉。这个是关键的一步，这一步就是如何设计抽屉。根据题目条件和结论，结合有关的数学知识，抓住最基本的数量关系，设计和确定解决问题所需的抽屉及其个数，为使用抽屉铺平道路。最后运用抽屉原理。观察题设条件，结合第二步，恰当应用各个原则或综合运用几个原则，以求问题之解决。 下面两个典型例题的解题过程充分展现了抽屉原理的解题过程，希望读者能有所体会。 例1：证明任取6个自然数，必有两个数的差是5的倍数。 证明：考虑每个自然数被5除所得的余数。即自然数可以作为物品，被5除所得余数可以作为抽屉。显然可知，任意一个自然数被5除所得的余数有5种情况：0，1，2，3，4。所以构造5个抽屉，每个抽屉中所装的物品就是被5除所得余数分别为0，1，2，3，4的自然数。运用抽屉原理，考虑“最坏” 的情况，先从每个抽屉中各取一个“物品”，共5个，则再取一个物品总能在先取的5个中找到和它出自于同一抽屉的“物品”，即它们被5除余数相同，所以它们的差能整除5。 组合数学课后标准答案 ————————————————————————————————作者：————————————————————————————————日期： 习题二证明：在一个至少有2人的小组中，总存在两个人，他们在组内所认识的人数相同。证明：假设没有人谁都不认识：那么每个人认识的人数都为[1,n-1]，由鸽巢原理知，n个人认识的人数有n-1种，那么至少有2个人认识的人数相同。假设有1人谁都不认识：那么其他n-1人认识的人数都为[1,n-2]，由鸽巢原理知，n-1个人认识的人数有n-2种，那么至少有2个人认识的人数相同。假设至少有两人谁都不认识，则认识的人数为0的至少有两人。 任取11个整数，求证其中至少有两个数的差是10的整数倍。证明：对于任意的一个整数，它除以10的余数只能有10种情况：0，1，…，9。现在有11个整数，由鸽巢原理知，至少有2个整数的余数相同，则这两个整数的差必是10的整数倍。证明：平面上任取5个坐标为整数的点，则其中至少有两个点，由它们所连线段的中点的坐标也是整数。2.3证明：有5个坐标，每个坐标只有4种可能的情况：（奇数，偶数）；（奇数，奇数）；（偶数，偶数）；（偶数，奇数）。由鸽巢原理知，至少有2个坐标的情况相同。又要想使中点的坐标也是整数，则其两点连线的坐标之和为偶数。因为奇数+奇数= 偶数；偶数+偶数=偶数。因此只需找以上2个情况相同的点。而已证明：存在至少2个坐标的情况相同。证明成立。 一次选秀活动，每个人表演后可能得到的结果分别为“通过”、“淘汰”和“待定”，至少有多少人参加才能保证必有100个人得到相同的结果？证明：根据推论2.2.1，若将3*（100-1）+1=298个人得到3种结果，必有100人得到相同结果。一个袋子里装了100个苹果、100个香蕉、100个橘子和100个梨。那么至少取出多少水果后能够保证已经拿出20个相同种类的水果？证明：根据推论2.2.1，若将4*（20-1）+ 1 = 77个水果取出，必有20个相同种类的水果。 抽屉原理及其简单应用 一、知识要点 抽屉原理又称鸽巢原理，它是组合数学的一个基本原理，最先是由德国数学家狄利克雷明确地提出来的，因此，也称为狄利克雷原理。 把3个苹果放进2个抽屉里，一定有一个抽屉里放了2个或2个以上的苹果。这个人所皆知的常识就是抽屉原理在日常生活中的体现。用它可以解决一些相当复杂甚至无从下手的问题。 原理1：把n+1个元素分成n类，不管怎么分，则一定有一类中有2个或2个以上的元素。原理2：把m个元素任意放入n（n≤m）个集合，则一定有一个集合至少要有k个元素。其中k＝m/n（当n能整除m时）或k＝〔m/n〕＋1（当n不能整除m时），这里〔m/n〕表示不大于m/n的最大整数，即m/n的整数部分。 原理3：把无穷多个元素放入有限个集合里，则一定有一个集合里含有无穷多个元素。二、应用抽屉原理解题的步骤 第一步：分析题意。分清什么是“东西”，什么是“抽屉”，也就是什么作“东西”，什么可作“抽屉”。 第二步：制造抽屉。这个是关键的一步，这一步就是如何设计抽屉。根据题目条件和结论，结合有关的数学知识，抓住最基本的数量关系，设计和确定解决问题所需的抽屉及其个数，为使用抽屉铺平道路。 第三步：运用抽屉原理。观察题设条件，结合第二步，恰当应用各个原则或综合运用几个原则，以求问题之解决。 三、应用抽屉原理解题例举: 1.张叔叔参加飞镖比赛，投了5镖，成绩是41环。张叔叔至少有一镖不低于9环。为什么？（教科书P73 T2） 解答：这道题物体个数和抽屉都比较明显。成绩41环看作个数，5镖看作抽屉，列式为：41÷5=8……1 8+1=9 2．有9支球队进行比赛，已经赛了10场，那么总有一支球队至少赛了几场？ 解答：有些题目物体的个数没有直接告诉我们。根据问题至少赛了几场，那我们要知道已经赛过的总的场次。根据已经赛了10场，每场2支球队，总场次应该是20次。这就是物体的个数。9支球队可以看作抽屉。根据今天所教的知识（原理2）我们知道20÷9=2……2，2+1=3 3.有红、黄两种颜色在下面的长方形格子中随意涂色，每个格子涂一种颜色。青青发现无论怎样涂，至少有两列涂法完全相同。请你先试一试，再说明理由。（作业本P29 T4） 解答：根据至少有两列涂法完全相同。我们要知道总的列数。这道题已经知道物体的个数是5列。但抽屉的个数却掩藏起来，我们需要根据排列知识找出抽屉的个数。已知颜色有2种，在一列的排列组合中有这么4种情况。（红红、红黄、黄黄、黄红）所以可以做成4个抽屉。用算式5÷4=1……1，1+1=2就说明问题。 4．任意写出5个非零的自然数，我能找到两个数，让这两个数的差是4的倍数。（作业本P29 T5） 解答：这题已经告诉我们物体的个数是5。但什么做为抽屉？要做几个抽屉却需要我们去构建。根据条件4的倍数，我们知道一个数除以4没有余数那就是4的倍数，在这些数中除以4的过程中会出现这四种情况（整除、余数是1、2、3）那就可以根据这四种情况做成四个 组合数学 例1: 将8个“车”放在8×8的国际象棋棋盘上，如果它们两两均不能互吃，那么称8个“车”处于一个安全状态。问共有多少种不同的安全状态? 解：8个“车”处于安全状态当且仅当它们处于不同的8行和8列上。 用一个排列a1,a2,…,a8 ，对应于一个安全状态，使ai 表示第i 行的ai 列上放置一个“车”。这种对应显然是一对一的。因此，安全状态的总数等于这8个数的全排列总数8!＝40320。 例4：n 位客人在晚会上每人与他人握手d 次，d 是奇数。证明n 偶数。 证：由于每一次握手均使握手的两人各增加 一次与他人握手的次数，因此n 位客人与他人握手 次数的总和 nd 是偶数 — 握手次数的2倍。根据奇偶 性质，已知d 是奇数，那么n 必定是偶数。 例４ 从1到2n 的正整数中任取n +1个，则这n +1个数中，至少有一对数，其中一个是另一个的倍数。 证 设n +1个数是a 1, a 2, ···, an +1。每个数去掉一切2的因子，直至剩下一个奇数为止。组成序列r 1, r 2,, ···, rn +1。这n +1个数仍在[1 , 2n ]中，且都是奇数。而[1, 2n ]中只有n 个奇数，故必有ri =rj = r , 则ai = 2αi r , aj = 2αj r 。若ai ＞aj ，则ai 是aj 的倍数。 例5 设a 1, a 2, ···, am 是正整数，则至少存在一对k 和l , 0≤k 李凡长版-组合数学课后习题答案-习题3 第三章递推关系 1.在平面上画n条无限直线,每对直线都在不同的点相交,它们构成的无限 区域数记为f(n),求f(n)满足的递推关系. 解： f(n)=f(n-1)+2 f(1)=2,f(2)=4 解得f(n)=2n. 2.n位三进制数中,没有1出现在任何2的右边的序列的数目记为f(n),求 f(n)满足的递推关系. 解：设a n-1a n-2 …a 1 是满足条件的n-1位三进制数序列，则它的个数可以用f(n-1) 表示。 a n 可以有两种情况： 1）不管上述序列中是否有2，因为a n 的位置在最左边，因此0 和1均可选； 2）当上述序列中没有1时，2可选； 故满足条件的序列数为 f(n)=2f(n-1)+2n-1 n 1, f(1)=3 解得f(n)=2n-1(2+n). 3.n位四进制数中,2和3出现偶数次的序列的数目记为f(n),求f(n)满足 的递推关系. 解：设h(n)表示2出现偶数次的序列的数目，g(n)表示有偶数个2奇数个3的序列的数目，由对称性它同时还可以表示奇数个2偶数个3的序列的数目。 则有 h(n)=3h(n-1)+4n-1-h(n-1),h(1)=3 （1） f(n)=h(n)-g(n),f(n)=2f(n-1)+2g(n-1) （2） 将（1）得到的h(n)=(2n+4n)/2代入（2），可得 n+4n)/2-2f(n), 4.求满足相邻位不同为0的n位二进制序列中0的个数f(n). 解：这种序列有两种情况： 1)最后一位为0，这种情况有f(n-3)个； 2)最后一位为1，这种情况有2f(n-2)个； 所以 f(1)=2,f(2)=3,f(3)=5. 5.求n位0,1序列中“00”只在最后两位才出现的序列数f(n). 解：最后两位是“00”的序列共有2n-2个。 f(n)包含了在最后两位第一次出现“00”的序列数，同时排除了在n-1位第一次出现“00”的可能； f(n-1)表示在第n-1位第一次出现“00”的序列数，同时同时排除了在n-2位第一次出现“00”的可能； 依此类推，有 17 第十三章 排列组合与概率 一、基础知识 1．加法原理：做一件事有n 类办法，在第1类办法中有m 1种不同的方法，在第2类办法中有m 2种不同的方法，……，在第n 类办法中有m n 种不同的方法，那么完成这件事一共有N=m 1+m 2+…+m n 种不同的方法。2 乘法原理：做一件事，完成它需要分n 个步骤，第1步有m 1种不同的方法，第2步有m 2种不同的方法，……，第n 步有m n 种不同的方法，那么完成这件事共有N=m 1×m 2×…×m n 种不同的方法。3．排列与排列数：从n 个不同元素中，任取m(m ≤n)个元素，按照一定顺序排成一列，叫做从n 个不同元素中取出m 个元素的一个排列，从n 个不同元素中取出m 个(m ≤n)元素的所有排列个数，叫做从n 个不同元素中取出m 个元素的排列数，用m n A 表示，m n A =n(n-1)…(n-m+1)= )! (! m n n -,其中m,n ∈N,m ≤n, 注：一般地0 n A =1，0！=1，n n A =n!。 4．N 个不同元素的圆周排列数为n A n n =(n-1)!。 5．组合与组合数：一般地，从n 个不同元素中，任取m(m ≤n)个元素并成一组，叫做从n 个不同元素中取出m 个元素的一个组合，即从n 个不同元素中不计顺序地取出m 个构成原集合的一个子集。从n 个不同元素中取出m(m ≤n)个元素的所有组合的个数，叫做从n 个不同元素中取出m 个元素的组合数，用m n C 表示： .)! (!! !)1()1(m n m n m m n n n C m n -=+--= 6．组合数的基本性质：（1）m n n m n C C -=；（2）1 1--+=n n m n m n C C C ；（3） k n k n C C k n =--11；（4）n n k k n n n n n C C C C 20 10==+++∑= ；（5）111++++-=+++k m k k m k k k k k C C C C ；（6） k n m n m k k n C C C --=。 7．定理1：不定方程x 1+x 2+…+x n =r 的正整数解的个数为1 1--n r C 。 抽屉原理及其应用 许莉娟 （数学科学学院，2003 （ 4）班，03213123号） ［摘要］抽屉原理是数学中的重要原理，在解决数学问题时有非常重要的作用.各种形式的抽屉原理在高等数学和初等数学中经常被采用.本文着重从抽屉的构造方法阐述抽屉原理在高等数学和初等数学（竞赛题）中的应用，同时指岀了它在 应用领域中的不足之处. ［关键词］抽屉原理高等数学初等数学 抽屉原理也称为鸽笼原理或鞋箱原理，它是组合数学中的一个最基本的原理.抽屉原 理主要用于证明某些存在性问题及必然性题目，如几何问题、涂色问题等?抽屉原理的简 单形式可以描述为：“如果把n ? 1个球或者更多的球放进n个抽屉，必有一个抽屉至少有两个球.”它的正确性十分明显，很容易被并不具备多少数学知识的人所接受，如果将其灵活地运用，则可得到一些意想不到的效果. 各种形式的抽屉原理在高等数学和初等数学中经常被采用，使用该原理的关键在于如何巧妙地构造抽屉，即如何找出合乎问题条件的分类原则，抽屉构造得好，可得出非常巧妙的结论，下面我们着重从抽屉的构造途径去介绍抽屉原理在高等数学和初等数学（竞赛题）中的应用，同时指出它在应用领域中的不足之处? 一、抽屉原理 陈景林、阎满富编著的中国铁道出版社出版的《组合数学与图论》一书中对抽屉原理给出了比较具体的定义，概括起来主要有下面几种形式： 原理I把多于n个的元素按任一确定的方式分成n个集合，则一定有一个集合中含有两个或两个以上的元素? 原理U把m个元素任意放到n（m ? n）个集合里，则至少有一个集合里至少有 k个元素，其中 当n能整除m时， 当n不能整除m时. 原理川把无穷个元素按任一确定的方式分成有穷个集合，则至少有一个集合中仍含无穷个 第九讲 抽屉原理 一、 知识点： 1． 把27个苹果放进4个抽屉中，能否使每个抽屉中苹果数均小于等于6？那么至少有一 个抽屉中的苹果数大于等于几？ 2． 把25个苹果放进5个抽屉中，能否使每个抽屉中苹果数均小于等于4？那么至少有一 个抽屉中的苹果数大于等于几？ 上述两个结论你是如何计算出来的？ ★规律：用苹果数除以抽屉数，若余数不为零，则“答案”为商加1，若余数为零，则“答 案”为商。 ★抽屉原则一： 把n 个以上的苹果放到n 个抽屉中，无论怎样放，一定能找到一个抽屉，它里面至少有两个苹果。 ★抽屉原则二： 把多于m ×n 个苹果放到n 个抽屉中,无论怎样放,一定能找到一个抽屉,它里面至少有(m +1)个苹果。 二、 基础知识训练（再蓝皮书） 1、 把98个苹果放到10个抽屉中， 无论怎么放， 我们一定能找到一个含苹果最多的抽屉，它里面至少含有 个苹果。 2、1000只鸽子飞进50个巢，无论怎么飞，我们一定能找到一个含鸽子最多的巢， 它里面至少含有 只鸽子。 3、从8个抽屉中拿出17个苹果，无论怎么拿。我们一定能找到一个拿苹果最多的 抽屉，从它里面至少拿出了 个苹果。 4、从 个抽屉中（填最大数）拿出25个苹果，才能保证一定能找到一个抽屉， 从它当中至少拿了7个苹果。 三、 思路与方法： 在抽屉原理问题，难在有些题目抽屉没有直接给出，要求我们自己根据题意去造抽屉，但我们也不要为此感到困难，往往在题目有一句关键的话，告诉我们抽屉的性质，我们可以根据此性质来构造抽屉即可。 训 练 题 1． 六（1）班有49名学生。数学王老师了解到在期中考试中该班英文成绩除3人外均在86 分以上后就说：“我可以断定，本班同学至少有4人成绩相同。”请问王老师说的对吗？为什么？ 2． 从100,,3,2,1 这100个数中任意挑选出51个数来，证明在这51个数中，一定： （1）有2个数互质； （2）有两个数的差为50； 3． 圆周上有2000个点，在其上任意地标上1999,,2,1,0 （每一点只标一个数，不同的点 组合数学作业 第一章引言 Page 13, ex3,4,7,30 ex3. 想象一座有64个囚室组成的监狱，这些囚室被排列成8 8棋盘。所有相邻的囚室间都有门。某角落处意见囚室例的囚犯被告知，如果他能够经过其它每一个囚室正好一次之后，达到对角线上相对的另一间囚室，那么他就可以获释。他能获得自由吗？ 解：不能获得自由。 方法一：对64个囚室用黑白两种颜色染色，使得横和竖方向相邻的囚室颜色不同。则对角线上两个囚室颜色为同黑或同白。总共偶数个囚室，若能遍历且不重复，则必然是黑出发白结束，矛盾。 方法二：64个囚室，若要经过每个囚室正好一次，需要走63步，即奇数步。 不妨假设该囚犯在第1行第1列，那么到第8行第8列，横着的方向需要走奇数步，竖着的方向需要走奇数步，即总共需要偶数步。 所以不能恰好经过每个囚室一次到达对角线上的囚室。 ex4. (a) 设f(n)是用多米诺牌(2-牌)对2×n棋盘作完美覆盖的个数。估计一下f(1),f(2),f(3),f(4)和f(5). 试寻找(或证明)这个计数函数f满足的简单关系。利用这个关系计算f(12)。 (b) 设g(n)是用多米诺牌(2-牌)对3×n棋盘作完美覆盖的个数。估计g(1),g(2),…,g(6). 解：(a) f(1)=1, f(2)=2, f(3)=3, f(n+2)=f(n+1)+f(n) f(4)=f(3)+f(2)=5, f(5)=f(4)+f(3)=8 f(6)=f(5)+f(4)=13 f(7)=f(6)+f(5)=21 f(8)=f(7)+f(6)=34 f(9)=f(8)+f(7)=55 f(10)=f(9)+f(8)=89 f(11)=f(10)+f(9)=144 f(12)=f(11)+f(10)=233 (b) g(1)=0, g(2)=3, g(3)=0, g(4)=9+2=11, g(n+4)=4g(n+2)-g(n), g(5)=0, g(6)=41. ex7. 设a和b是正整数，且a是b的因子。证明m×n棋盘有a×b的完美覆盖当且仅当a 既是m又是n的因子，而b是m或n的因子。(提示: 把a×b牌分割成a个1×b牌。) 解：充分性。当a既是m又是n的因子，而b是m或n的因子，则m×n棋盘有a×b的平凡完美覆盖。 必要性。假设m×n棋盘有a×b牌的完美覆盖。则m×n棋盘必有b牌的完美覆盖。根据书中的定理，b是m的因子或n的因子。 下面证明a既是m的因子又是n的因子。 方法一: 因为a是b的因子，所以a×b牌可以分割成b/a个a×a牌。m×n棋盘有a×a的完美覆盖，则必然有a×a牌的完美覆盖。而a×a牌是正方形的，所以只有唯一的一种平凡覆盖方式。从而m是a的倍数，n也是a的倍数。 方法二: 因为a是b的因子，不妨设b=ka。由m×n棋盘有a×b牌的完美覆盖，可任取一个完美覆盖。设第一行的n个方格由p个a×b牌和q个b×a牌盖住，则有n=pb+qa=(pk+q)a，所以n是a的倍数。同理，m也是a的倍数。 教案 抽屉原理 1、概念解析 把3个苹果任意放到两个抽屉里，可以有哪些放置的方法呢一个抽屉放一个，另一个抽屉放两个；或3个苹果放在某一个抽屉里.尽管放苹果的方式有所不同，但是总有一个共同的规律：至少有一个抽屉里有两个或两个以上的苹果.如果把5个苹果任意放到4个抽屉里，放置的方法更多了，但仍有这样的结果.由此我们可以想到，只要苹果的个数多于抽屉的个数，就一定能保证至少有一个抽屉里有两个或两个以上的苹果.道理很简单：如果每个抽屉里的苹果都不到两个（也就是至多有1个），那么所有抽屉里的苹果数的和就比总数少了.由此得到： 抽屉原理：把多于n个的苹果放进n个抽屉里，那么至少有一个抽屉里有两个或两个以上的苹果。 如果把苹果换成了鸽子，把抽屉换成了笼子，同样有类似的结论，所以有时也把抽屉原理叫做鸽笼原理.不要小看这个“原理”，利用它可以解决一些表面看来似乎很难的数学问题。 比如，我们从街上随便找来13人，就可以断定他们中至少有两个人属相（指鼠、牛、虎、兔、…等十二种生肖）相同.怎样证明这个结论是正确的呢只要利用抽屉原理就很容易把道理讲清楚.事实上，由于人数（13）比属相数（12）多，因此至少有两个人属相相同（在这里，把13人看成13个“苹果”，把12种属相看成12个“抽屉”）。 应用抽屉原理要注意识别“抽屉”和“苹果”，苹果的数目一定要大于抽屉的个数。 2、例题讲解 例1 有5个小朋友，每人都从装有许多黑白围棋子的布袋中任意摸出3枚棋子.请你证明，这5个人中至少有两个小朋友摸出的棋子的颜色的配组是一样的。 例2 一副扑克牌（去掉两张王牌），每人随意摸两张牌，至少有多少人才能保证他们当中一定有两人所摸两张牌的花色情况是相同的 例3 从2、4、6、…、30这15个偶数中，任取9个数，证明其中一定有两个数之和是34。 习题二 2.1证明：在一个至少有2人的小组中，总存在两个人，他们在组内所认识的人数相同。 证明： 假设没有人谁都不认识：那么每个人认识的人数都为[1,n-1]，由鸽巢原理知，n个人认识的人数有n-1种，那么至少有2个人认识的人数相同。 假设有1人谁都不认识：那么其他n-1人认识的人数都为[1,n-2]，由鸽巢原理知，n-1个人认识的人数有n-2种，那么至少有2个人认识的人数相同。 假设至少有两人谁都不认识，则认识的人数为0的至少有两人。 2.2任取11个整数，求证其中至少有两个数的差是10的整 数倍。 证明：对于任意的一个整数，它除以10的余数只能有10种情况：0，1，…，9。现在有11个整数，由鸽巢原理知，至少有2个整数的余数相同，则这两个整数的差必是10的整数倍。 2.3证明：平面上任取5个坐标为整数的点，则其中至少有 两个点，由它们所连线段的中点的坐标也是整数。 2.3证明： 有5个坐标，每个坐标只有4种可能的情况：（奇数，偶数）；（奇数，奇数）；（偶数，偶数）；（偶数，奇数）。由鸽巢原理知，至少有2个坐标的情况相同。又要想使中点的坐标也是整数，则其两点连线的坐标之和为偶数。因为奇数+奇数= 偶数；偶数+偶数=偶数。因此只需找以上2个情况相同的点。而已证明：存在至少2个坐标的情况相同。证明成立。 2.4一次选秀活动，每个人表演后可能得到的结果分别为“通 过”、“淘汰”和“待定”，至少有多少人参加才能保证必有100个人得到相同的结果？ 证明： 根据推论2.2.1，若将3*（100-1）+1=298个人得到3种结果，必有100人得到相同结果。 2.5一个袋子里装了100个苹果、100个香蕉、100个橘子和100个梨。那么至少取出多少水果后能够保证已经拿出20个相同种类的水果？ 证明： 根据推论2.2.1，若将4*（20-1）+ 1 = 77个水果取出，必有20个相同种类的水果。 组合数学试题 共 5 页 ，第 1 页 电子科技大学研究生试卷 （考试时间： 至 ，共 2 小时） 课程名称 组合数学 教师 学时 40 学分 2 教学方式 讲授 考核日期 2009 年 12 月 日 成绩 考核方式： （学生填写） 一、(14分) 现安排从星期一至星期五对5个项目A, B, C, D, E 进行评审，每个项目安排一天，每天安排一个项目。但要求项目A 不安排在星期二评审，项目B 不安排在星期三和星期五评审，项目C 不安排在星期四评审，项目D 不安排在星期一评审，项目E 不安排在星期三和星期四评审。问有多少种不同的评审安排方案？ 解 原问题可模型化为一个5元有禁位的排列. 其禁区棋盘C 如下图的阴影部分。 -----------------4分 由图,可得C 的棋盘多项式为 R(C)= = 1+7x+17x 2+18x 3+8x 4+x 5 -----------------5分 所以安排方案数为 5! - 7·4! + 17·3! - 18·2! + 8-1 -----------------4分 = 25 即共有25种。 -----------------1分 二、（10分）用2种颜色对下图的小圆点着色，证明必存在两列，其着色完全相同。 证明：因每个小圆点有2种颜色可选,故每列恰有8 种着色方案, -------------5分 学 号 姓 名 学 院 …… … …… …… …密 …… …… … 封 … … … … … 线 … … … … … 以 … … … … … 内 … … … … … 答 … …… … … 题 … …… … … 无 … … … … … 效… … … …… …… … A B C D E 1 2 3 4 5 排列组合问题专项讲义 知识点+例题+练习题+详细解析 基本知识框架： 加法原理 排列数 排列数公式 综合应用 乘法原理 组合数 组合数公式 一、基本概念： 乘法原理： 一般地，如果完成一件事情需要n 步，其中，做第一步有a 种不同的方法，做第二步有b 种不同的方法，…，做第n 步有x 种不同的方法，那么，完成这件事一共有： N ＝a ×b ×…×x 种不同的方法。 加法原理： 一般地，如果完成一件事有k 类方法，第一类方法中有a 种不同的做法，第二类方法中有b 种不同的做法，…，第n 类有x 种不同的做法，那么，完成这件事一共有： N ＝a ＋b ＋…＋x 种不同的方法。 排列、排列数 一般地，从n 个不同的元素中任意取出m(n ≥m)个元素，按照一定的顺序排成一列，叫做从n 个不同的元素中取出m 个元素的一个排列。 从n 个不同的元素中取出m(n ≥m)个元素的所有排列的个数，叫做从n 个不同的元素中取出m 个元素 的排列数。记做m n A 。 m n A ＝n(n －1)(n －2)(n －3)…(n －m ＋1) 组合、组合数 一般地，从n 个不同的元素中取出m(n ≥m)个元素组成一组，不计组内各元素的次序，叫做从n 个不同的元素中取出m 个元素的一个组合。 从n 个不同的元素中取出m(n ≥m)个元素的所有组合的个数，叫做从n 个不同的元素中取出m 个不同 元素的组合数。记座m n C 。 m n C ＝m n m m A A ＝n(n －1)(n －2)(n －3)…(n －m ＋1)÷!m 二、常见的解题策略 1、特殊元素优先排列 2、合理分步与准确分类 3、排列、组合混合问题先选后排 4、正难则反，等价转化 5、相邻问题捆绑法 6、不相邻问题插空法 7、定序问题除法处理 组合数学题库答案 填空题 1．将5封信投入3个邮筒，有_____243 _种不同的投法． 2．5个男孩和4个女孩站成一排。如果没有两个女孩相邻，有 43200 方法． 3．22件产品中有2件次品，任取3件，恰有一件次品方式数为__ 380 ______． 4．6()x y +所有项的系数和是_64_ _．答案：64 5．不定方程1232++=x x x 的非负整数解的个数为_ 6 ___． 6．由初始条件f f (0)1,(1)1==及递推关系)()1()2(n f n f n f ++=+确定的数列f n n {()}(0)≥叫做Fibonacci 数列 7．（3x-2y ）20 的展开式中x 10y 10的系数是101010 20)2(3-c ． 8．求6的4拆分数P 4(6)= 2 ． 9．已知在Fibonacci 数列中，已知f f f (3)3,(4)5,(5)8===，试求Fibonacci 数f (20)=10946 10．计算P 4(12)= k k P P P P P P 4 412341(12)(12)(8)(8)(8)(8) ===+++∑k k k k P P P P 34 121 1 (8)(8)(5)(4)145515===+++=+++=∑∑ 11．P 4(9)=（ D ）A ．5 B. 8 C. 10 D. 6 12．选择题 1．集合A a a a 1210{,,,}=的非空真子集的个数为（ A ）A.1022 B.1023 C. 1024 D.1021 2．把某英语兴趣班分为两个小组，甲组有2名男同学，5名女同学；乙组有3名男同学，6名女同学，从甲乙两组均选出3名同学来比赛，则选出的6人中恰有1名男同学的方式数是（ D ） A ．800 B. 780 C. 900 D. 850 3．设x y (,)满足条件x y 10+≤，则有序正整数对x y (,)的个数为（ D ） A. 100 B.81 C. 50 D.45 4．求60123(32)+++x x x x 中x x x 23 012项的系数是（ C ） A.1450 B. 60 C.3240 D.3460 5．多项式40123(24)x x x x +++中项2 20 12x x x ??的系数是（ C ） A ．78 B. 104 C. 96 D. 48 6．有4个相同的红球，5个相同的白球，那么这9个球有（ B ）种不同的排列方式 A. 63 B. 126 C. 252 D.378 7．递推关系f n f n f n ()4(1)4(2)=---的特种方程有重根2，则（B ）是它的一般解(完整word版)组合数学课后答案
组合数学题库答案.docx
抽屉原理公式及例题精编版
组合数学课后答案
高中数学竞赛标准讲义---排列组合与概率
抽屉原理的经典解题思路
组合数学课后标准答案
抽屉原理及其简单应用
组合数学题目及标准答案
李凡长版-组合数学课后习题答案-习题3
数学竞赛教案讲义排列组合与概率
抽屉原理及其应用
抽屉原理精华及习题(附答案)
组合数学作业答案1-2章2016
小学奥数：抽屉原理(含答案)
组合数学 课后答案
组合数学 试题及答案09
排列组合专项讲义(知识点+例题+练习含详解)
组合数学题库答案备课讲稿
相关主题
文本预览