组合数学讲义 5章 抽屉原理

第五章 抽屉原理和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 3651365-

特例：()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 -=-∑∑==111

与假设矛盾。

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 αα22==，r r a k k k k α

α22==，显然有：要么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

-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 119=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组的任何一组中，与题设矛盾。

(证) 某个序列{}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 相等，设

121+===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 mod ≡， ()()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 mod ≡， ()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

1j j XA ＝∑=40111j ＝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 ，即4010，设为r q ()k r r ≠≤≤；201，由题意知必存在某个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 ，于是 402140111==+

=+i i i i C A X ＝1＋∑=402

1i 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

361333132>-=++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 ≤，即222i i r

r a b b a ≤???? ?? ， i=1,2,…,n 因此

()

222212n r r b b b b a +++???? ?? ≤22221n 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 ，122221=+++n b b b ，则结论变为

11b a ，22b 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，当n ＝5时，按照图中的涂法，是不存在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时，对集合V 中的元素，下面结论至少有一个成立：

（1） 存在3个元素，其全部二元子集都属于1S ；

（2） 存在3个元素，其全部二元子集都属于2S 。

图5.3.1 无同色3K 的五边形染色方案

而当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。另一方面，设9K 中实有红色（蓝色）线段共m 条，

现在对这m 条边的每个端点逐点统计由它们发出的红色（蓝色）线段的条数，由于每条线段有两个端点，故应为2m 。 于是得出2m ＝27，这是不可能的。引理得证。

定理5.3.1. 对9K 涂以红蓝两色，必定会出现一个同色的3K 或同色4K 。

(证) 设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 又无蓝色4K 的八边形染色方案

（实线——红色，虚线——蓝色）

注：但存在蓝色的3K 。

5.4 R a m s e y 数

由§5.3.3受到启发，对于给定的正整数p 、q ≥2，是否存在一个最小的正整数r ，具有下述性质：对完全图n K 的每条边涂以颜色1C 或2C ，当n ≥r 时，在n K 中必含有一个完全子图p K ，其所有边涂的是颜色1C （即同色p K ），或含有一个完全子图q K ，其所有边涂的是颜色2C （即同色q K ）。答案是肯定的。

定义5.4.1 满足上述条件的数r 称为Ramsey 数，记为r(p,q;2)，简记为r(p,q)。

至此，我们已经知道r(3,3)＝6，r(3,4)＝9。

例5.4.1 证明r(4,4)＝18。

（证）设17210v v v v ,,,, 是完全图18K 的顶点，现考察18K 中

从0v 出发的17条线段，它们分成了红、蓝两类，由抽屉原

理可知：至少有9条是同色的，不妨设它们为红色（蓝色）。进一步再来考察这9条红色（蓝色）线段里，异于0v 的9

组合数学题库答案.docx

填空题 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

小学奥数：抽屉原理(含答案)

教案 抽屉原理 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。

抽屉原理公式及例题精编版

抽屉原理公式及例题“至少……才能保证(一定)…最不利原则 抽屉原则一：如果把(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份。要找到两个手机号码后两位相同的被调查者，首先要确定手机号码后两位有几种不同的排列方式。因为每一位

(完整word版)组合数学课后答案

习题二证明：在一个至少有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个相同种类的水果。

高中数学竞赛标准讲义---排列组合与概率

高中数学竞赛标准讲义----排列组合与概率 一、基础知识 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．经历“抽屉原理”的探究过程，初步了解“抽屉原理”，会用“抽屉原理”解决简单的实际问题。 2．通过猜测、验证、观察、分析等数学活动，建立数学模型，发现规律。渗透“建模”思想。 3、经历从具体到抽象的探究过程，提高学生有根据、有条理地进行思考和推理的能力。 4、通过“抽屉原理”的灵活应用，提高学生解决数学问题的能力和兴趣，感受到数学文化及数学的魅力。 【教学重、难点】经历“抽屉原理”的探究过程，理解“抽屉原理”，并对一些简单实际问题加以“模型化”。 【教学准备】 1、教学ppt课件 2、铅笔120支 (小棒代替) ，笔盒100个（杯子代替），每个小组3个杯子，5支小棒；扑克牌1副，凳子4把。 【教学流程】 一、问题引入。 师：在上课前，老师特别想和同学们做个游戏，谁愿来？老师准备了4把椅子，请5 位同学上来。

1．游戏要求：老师喊“准备”，你们5位同学围着椅子走动，等老师喊“开始”后请你们5个都坐在椅子上，每个人都必须坐下。 2.师：“准备”，“开始”，他们都坐好了吗？老师不用看就知道总有一把椅子上至少坐着两名同学，是这样的吗？如果反复再做，还会是这样的结果吗？ （游戏开始，让学生初步体验不管怎么坐，总有一把椅子上至少坐两个同学，使学生明确这是现实生活中存在着的一种现象。） 3、引入：看来，不管怎么坐，总有一把椅子上至少坐两个同学。你知道这是什么道理吗？这其中蕴含着一个有趣的数学原理，这节课我们就一起来研究这个原理。 4、明确学习目标与任务： 师：看到这个课题，你能想到这节课我们将要学习哪些知识吗？（学生表达想法） 课件出示学习目标与要求 1）、了解“抽屉原理”，会用“抽屉原理”解决简单的实际问题。 2）通过实验操作、自主探究、小组合作发现抽屉原理。 3）感受数学文化的魅力，提高对数学的兴趣。 二、探究新知 （一）教学例1 为了研究这个原理，我们做一组实验。 1、观察猜测 课件出示例1：把4支铅笔放进3个文具盒中，不管怎么放总有一个文具盒至少放 进____支铅笔。 猜一猜：不管怎么放，总有一个文具盒至少放进 ____支铅笔。

抽屉原理的经典解题思路

抽屉原理的经典解题思路 抽屉原理在公务员考试中的数字运算部分时有出现。抽屉原理是用最朴素的思想解决组合数学问题的一个范例，我们可以从日常工作中的实例来体会抽屉原理的应用。抽屉原理的内容简明朴素，易于接受，它在数学问题中有重要的作用。许多有关存在性的证明都可用它来解决。 先来看抽屉原理的一般叙述： 抽屉原理（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证明：在一个至少有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。 证明：

用抽屉原理解决问题

浙江省农村中小学现代远程教育工程资源建设多媒体教学课件 数学广角：用抽屉原理解决问题 使用范围：小学数学（人教版）六年级下册第五单元第72页 作者：高牡丹 单位：仙居县安洲小学 撰稿时间：2011年7月 ●教学目标： 1．进一步掌握抽屉原理，掌握抽屉原理的反向求法，会用“抽屉原理”解决简单的实际问题。 2．通过操作发展学生的类推能力，培养学生的发散性思维，形成比较抽象的数学思维。 3．通过“抽屉原理”的灵活应用感受数学的魅力，培学生大胆发表自己的见解和倾听他人意见，了解他人思维的好习惯。 ●教学重点： 用抽屉原理的逆向思维解决问题。 ●教学难点： 理解抽屉原理的反向求法并能灵活地运用抽屉原理解决问题。 ●教学准备： 多媒体课件、投影仪。 ●教学过程： 一、复习旧知 1、关于抽屉原理，我们已经知道了什么？ 小结：把一些物体放进几个抽屉中，不管怎么放，有一个抽屉里至少有物体个数÷抽屉个数“所得的商+1”个物体。 2、抽屉原理中的抽屉一定是指真正的抽屉吗？还可以指什么？

3.增加复习题：如：13人中至少有2个人的生肖是相同的，为什么？ 二、学习例3 1．出示例题，分析题意：盒子里有同样大小的红球和蓝球各4个。要想摸出的球一定有2个同色的，至少要摸出几个球？ （1）通读题目，你知道了什么？和咱们前两节课学的抽屉原理一样吗？怎么不一样？ 小结比较结果：已经知道了一个抽屉里至少有2个物体，求至少要摸出几个球。这节课我们是根据抽屉原理来解决问题的。板书课题：用抽屉原理解决问题。 （2）解决这个问题的关键是什么呢？是的，要先找到抽屉。抽屉是指什么？对啊，就是指红球和蓝球。 （3）有几个抽屉呢？你是怎么知道的？ 预设1：4个，因为题目中说红球和蓝球各4个。 预设2：2个，因为就只有两种球，红球和蓝球。 师：到底谁的说法是对的呢？请大家先在小组里讨论一下。 反馈：红球4个，蓝球4个，有种颜色，所以应该是2个抽屉。 2．解决问题：要想摸出的球一定有2个同色的，最少要摸出几个球？ （1）如果把这句话说完整：在2个抽屉里，最少摸出几个球就能保证一定有2个同色的？请大家思考一下。 （2）反馈： 生1：2个，摸两个球都是红色的，或者摸两个球都是蓝色的。 生2：不行，摸2个万一一个红球一个蓝球呢？应该是3个。 生3：摸出5个球，肯定有2个是同色的。因为红球和蓝球各4个。 （3）到底哪种说法是正确的呢？请大家在小组里讨论一下。 只摸2个球肯定是不行的，因为可能是一个红球、一个蓝球。 （有可能但不能保证） 根据5÷2=2……1，可以知道，摸出5个球时至少有3个球同色。因此，摸出5个球是没有必要的。（能保证但不是最少的） 得出结论：要想摸出的球一定有两个同色的，只要摸出的球比颜色种数多1，也就是比2多1，因此是3次。

抽屉原理及其简单应用

抽屉原理及其简单应用 一、知识要点 抽屉原理又称鸽巢原理，它是组合数学的一个基本原理，最先是由德国数学家狄利克雷明确地提出来的，因此，也称为狄利克雷原理。 把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）那就可以根据这四种情况做成四个

组合数学课后标准答案

组合数学课后标准答案

————————————————————————————————作者：————————————————————————————————日期：

习题二证明：在一个至少有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个相同种类的水果。

浅谈抽屉原理问题解题技巧

浅谈抽屉原理问题解题技巧 令狐采学 桌上有十个苹果，要把这十个苹果放到九个抽屉里，无论怎样放，我们会发现至少会有一个抽屉里面放两个苹果[是“至少两个苹果”吧？]。这一现象就是我们所说的“抽屉原理”。抽屉原理的一般含义为：如果每个抽屉代表一个集合，每一个苹果就可以代表一个元素，假如有n+1或多于n+1个元素放到n个集合中去，其中必定至少有一个集合里有两个元素[这个定义是有问题的。苹果的问题还可以认为抽屉不能空，“多于N+1个元素在n个集合中必定有两个元素的集合”无论集合空不空肯定是不对的。应该也是“至少两个元素”]。它是组合数学中一个重要的原理[这一段应该是百度百科里的内容。但是注意百科左边的图片里也是“至少有2个苹果”，下面的解析里的狄利克雷原则也是正确定义的。希望老师在引用的时候仔细分辨。]。抽屉原理看似简单，但它是近年来公考行测广大考生很容易丢分的部分。考生不能有效得分的主要原因：一是考生只是去背诵抽屉原理相关定理与公式；二是考生不能透彻理解应用“最不利原则”的思维角度。 目前，处理抽屉原理问题最基本和常用的方法是运用“最不利原则”，构造“最不利”“点最背”的情形。下面利用几道例题对抽屉原理问题的解法进行一下探讨。

一．基础题型 【例1】从一副完整的扑克牌中至少抽出（）张牌才能保证至少6张牌的花色相同？ A.21 B.22 C.23 D.24 解析：题目要求保证：6张牌的花色相同.考虑最不利情形：每种花色取5张，一共20张，然后抽出大小王共2张，总共22张，再抽取任意一张都能保证6张花色相同，共23张.因此，答案选C. 【例2】一副无“王”的扑克牌，至少抽取几张，方能使其中至少有两张牌具有相同的点数？（） A.10 B.11 C.13 D.14 解析：题目要求：两张牌具有相同的点数.考虑最不利情形：从中任取一种花色的牌13张，每张牌点数都不同，再抽取任何一张点数都会重复，总共抽取14张。因此，答案选D. 【例3】调研人员在一次市场调查活动中收回了435份调查试卷，其中80%的调查问卷上填写了被调查者的手机号码.那么调研人员至少需要从这些调查表中随机抽出多少份，才能保证一定能找到两个手机号码后两位相同的被调查者？（） A.101 B.175 C.188 D.200

组合数学题目及标准答案

组合数学 例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 h ，使得 ah+1+…+ ak= 39 证 令Sj= ，j =1 , 2 , …,100。显然 ∑=j i i a 1 ∑=h i i a 1

数学竞赛教案讲义排列组合与概率

第十三章 排列组合与概率 一、基础知识 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 （每一点只标一个数，不同的点

组合数学作业答案1-2章2016

组合数学作业 第一章引言 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：同年出生的400人中至少有2个人的生日相同。 解：将一年中的365天视为365个抽屉，400个人看作400个物体，由抽屉原理1可以得知：至少有2人的生日相同. 400/365=1…35,1+1=2又如：我们从街上随便找来13人，就可断定他们中至少有两个人属相相同。 “从任意5双手套中任取6只，其中至少有2只恰为一双手套。” “从数1，2，...，10中任取6个数，其中至少有2个数为奇偶性不同。” 例2：幼儿园买来了不少白兔、熊猫、长颈鹿塑料玩具，每个小朋友任意选择两件，那么不管怎样挑选，在任意七个小朋友中总有两个彼此选的玩具都相同，试说明道理. 解：从三种玩具中挑选两件，搭配方式只能是下面六种：（兔、兔），（兔、熊猫），（兔、长颈鹿），（熊猫、熊猫），（熊猫、长颈鹿），（长颈鹿、长颈鹿）。把每种搭配方式看作一个抽屉，把7个小朋友看作物体，那么根据原理1，至少有两个物体要放进同一个抽屉里，也就是说，至少两人挑选玩具采用同一搭配方式，选的玩具相同. 上面数例论证的似乎都是“存在”、“总有”、“至少有”的问题，不错，这正是抽屉原则的主要作用.（需要说明的是，运用抽屉原则只是肯定了“存在”、“总有”、“至少有”，却不能确切地指出哪个抽屉里存在多少. 抽屉原理虽然简单，但应用却很广泛，它可以解答很多有趣的问题，其中有些问题还具有相当的难度。下面我们来研究有关的一些问题。 制造抽屉是运用原则的一大关键 例1 从2、4、6、…、30这15个偶数中，任取9个数，证明其中一定有两个数之和是34。 分析与解答我们用题目中的15个偶数制造8个抽屉： 此抽屉特点：凡是抽屉中有两个数的，都具有一个共同的特点：这两个数的和是34。现从题目中的15个偶数中任取9个数，由抽屉原理（因为抽屉只有8个），必有两个数可以在同一个抽屉中（符合上述特点）.由制造的抽屉的特点，这两个数的和是34。 例2：从1、2、3、4、…、19、20这20个自然数中，至少任选几个数，就可以保证其中一定包括两个数，它们的差是12。