组合数学讲义及答案5章抽屉原理.pdf

《组合数学讲义及答案5章抽屉原理.pdf》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、《组合数学》第五章抽屉原理和Ramsey理论第五章抽屉原理和Ramsey理论概述：抽屉原理又称鸽巢原理或重叠原理，是组合数学中两大基本原理之一，是一个极其初等而又应用较广的数学原理。其道理并无深奥之处，且正确性也很明显。但若能灵活运用，便可能得到一些意料不到的结果。解决的问题：存在性问题，即在具体的组合问题中，要计算某些特定问题求解的方案数，其前提就是要知道这些方案的存在性。广义抽屉原理：1930年英国逻辑学家F.P.Ramsey将这个简单原理作了深刻推广，即Ramsey定理，也被称为广义抽屉原理。它是一个重要的组合定理，有许多应用。5.1抽屉原理（一）基本形式【定理5

2、.1.1】（基本形式）将n＋1个物品放入n个抽屉，则至少有一个抽屉中的物品数不少于两个。证反证之。将抽屉编号为：1,2,…,n，设第i个抽屉放有qi个物品，则q1q2qnn1但若定理结论不成立，即qi1，即有q1q2qn≤n，从而有n1qqqn12n矛盾。【例5.1.1】一年365天，今有366人，那么，其中至少有两人在同一天过生日。与概率的区别：抽屉原理讲的是所给出的结论是必然成立的，即100%成立。而概率反映的是不确定性现象发生的1/38《组合数学》第五章抽屉原理和Ramsey理论可能性问题，不讨论100%成立的确定性概率问题。生

3、日悖论：随机选出n个人，则其中至少有二人同一天出生的概率为nnPA＝1P365n365例如PA＝50.73%，PA＝99.99997%23100几何领域的另一著名悖论：【例5.1.2】箱子中放有10双手套，从中随意取出11只，则至少有两只是完整配对的。（二）推广形式【定理5.1.2】（推广形式）将qqqn1个物品放入n个抽屉，则下列事12n件至少有一个成立：即第i个抽屉的物品数不少于q个。i（证）反证。不然，设第i个抽屉的物品数小于qi（i＝1,2,…,n）(即该抽屉最多有q1个物品)，则有innnqin1＝物品总数≤qi1

4、qini1i1i1与假设矛盾。qqqn1＝12nq1q1q1112n（三）特例【推论1】将n(r－1)＋1个物品放入n个抽屉，则至少2/38《组合数学》第五章抽屉原理和Ramsey理论有一个抽屉中物品个数不少于r个。【推论2】将m个物品放入n个抽屉，则至少有一个m1m抽屉中物品个数不少于1＝个。其中x表nn示取x的整数部分，x表示不小于x的最小整数。【推论3】若n个正整数qi1,2,n满足iqqq12nr1n则至少存在一个q，满足qr。ii（四）例【例5.1.3】有

5、n位代表参加会议，若每位代表至少认识另外一个代表，则会议上至少有两人认识的人数相同。(证)设某代表认识的人数为k个，则k1,2,,n1（视为n－1个抽屉）。而会议上有n个代表，故每位代表认识的人数共为n个数（视为n个物品）。那么，由基本定理，结论成立。【例5.1.4】任意一群人中，必有两人有相同数目的朋友。(证)设有n个人n2，分三种情形讨论：(1)每人都有朋友，由例5.1.3即知结论成立；(2)只有一人无朋友，余下的n－1人都有朋友，由(1)知此n－1人中必有两人有相同数目的朋友；(3)有两人或两人以上的人无朋友，则朋友数为零的人已经有两个了，同样满足

6、条件。3/38《组合数学》第五章抽屉原理和Ramsey理论【例5.1.5】边长为2的正方形内有5个点，其中至少有两点，距离不超过2。(证)首先制造抽屉：将原正方形各对边中点相连，构成4个边长为1的小正方形（见图5.1.1(a)），视为抽屉。其次，由基本原理，至少有一个小正方形里点数不少于2。最后，从几何角度可以看出，同一小正方形内的两点的距离不超过小正方形的对角线之长度2，证毕。图5.1.1抽屉的选择注意：如果抽屉选择不当，可能于事无益。习题1、25.2应用§5.2.1抽屉原理的应用例5.2.1任意三个整数，必有两个之和为偶数（其差也为偶数）。(证)制造两个抽屉：“奇数

7、”和“偶数”，3个数放入两个抽屉，必有一个抽屉中至少有两个数，由整数求和的奇、偶性质即知此二数之和必为偶数。同理可知，二者之差也为偶数。4/38《组合数学》第五章抽屉原理和Ramsey理论任给3个整数，其中必存在两个整数，其和能被2整除。证明．记这3数为a,a,a，令ramod2123ii另则ri＝0，1（i＝1，2，3）。一以0，1为两个抽屉，3个a为物品，以r决定将a放提iii法入哪个抽屉。由抽屉原理，某个抽屉中至少有两个a，其除以2的i余数相同。那么，此2数即满足要求。问题：任给n个整数，其中必存在3个整数，其和能被3整除。问n最