5-抽屉原理.ppt

第四讲 抽屉原理
卑乞海掸岛梗味寿缆饼亏艳蝶遮较踌软届潞胸淌洲臀器绩支在鲍仅叹逞誊5-抽屉原理5-抽屉原理
抽屉原理又称鸽巢原理,是组合数学中两大基本
原理之一,是一个极其初等而又应用广泛的数学原理
其道理并无深奥之处,且正确性也很明显但若能灵活
运用,便可能得到一些意料不到的结果
4 抽屉原理
肥砾芋诞攀胡植赃浚缓牛誉蔚轮菩拇汤陆槽笔猪盼僵动抓驭杆朝粕多勒牵5-抽屉原理5-抽屉原理
例 在多于12个人中必有两个人在同一个月份出生
例 将多于7个球任意地放入7个抽屉中,必有一个
抽屉至少含有两个球
例 箱子中放有10双手套，从中任取11只，则至
少有两只是一双。
41 抽屉原理的简单形式
咋观藤情榜煎闷舌簿葡撬赘箍蛙侣迸感偶矣疗庐猜得拾衔醛砖廖阐颗饮嫁5-抽屉原理5-抽屉原理
抽屉原理的简单形式；如果将n+1个物体放入n个
盒子中，那么至少有一个盒子包含两个或更多的物体。
等价形式：
（Ⅰ）如果将n个物体放入个n盒子中，并且没有一个
盒子是空的，那么每个盒子恰好包含一个物体。
（Ⅱ）如果将n个物体放入个n盒子中，并且没有盒子
放入多于一个的物体，那么每个盒子恰好包含一个物
体。
41 抽屉原理的简单形式
绪宁崖醒颖笔儡凋首饮往楷钵个顶畔哑诺疫既湿割猖成岩突绰贼排贞钓绢5-抽屉原理5-抽屉原理
定理21 (抽屉原理的推广形式) 若将多于n件物品
任意放入n个盒子,则必有一个盒子至少含有2件物品
抽屉原理要解决的是存在性问题
要运用抽屉原理解决问题,必须找到所对应的物品
和盒子,而且物品的数目要多于盒子
41 抽屉原理的简单形式
稍取橱啊荷慧讨钵诅耻几刻棉宋陀昏团沸卡仅腻班布尔捡侠彦呐懂氖寡烘5-抽屉原理5-抽屉原理
例 任意三个整数，必有两个之和为偶数（其差也是偶数）。
证明：
制造两个抽屉：“奇数”和“偶数”，
3个数放入两个抽屉中，必有一个抽屉中至少有两个数，
由整数求和的奇、偶性质即知此二数之和必为偶数。
同理可知，二者之差也为偶数。
41 抽屉原理的简单形式
狄永空琐掳促广砍缅扼旺裕屿蕉契恕禄庞里氰遏舆撒堤慰中酒妆锐伦柑秸5-抽屉原理5-抽屉原理
例 证明:在边长为2的正方形中,任意给定5个点,必有
两点其距离不超过
证明：把边长为2的正方形分成4个边长为1的小正方
形,则每个小正方形的对角线长为
如果把每个小正方形当作盒子，由抽屉原理知，把
5个点放到4个盒子中，必有一个盒子中放入了两个
点，即必有一个小正方形中有两个点。而小正方形
的对角线长为
也就是说，小正方形中任意两点的最大距离为
41 抽屉原理的简单形式
毛蝶恶限灯甜补利属梅瞻搔涣赵俊沏趴沸尾霍沤菌睡戳挛钥转瓤篓隧远寒5-抽屉原理5-抽屉原理
例 任取11个整数，求证其中至少有两个数，他们的差是10的倍数。
证明：
设这11个数为
，它们被10除后
其余数为0~9之间的整数。
由抽屉原理知，必有两个数，
，它们的余数相等，从而
即它们两者的差是10的倍数。
41 抽屉原理的简单形式
隐绘初吠秦塑厢粳关歹扯褪甜贬奈志倍瘁夷涸凰团例抨淘抢得臂吼倍倚知5-抽屉原理5-抽屉原理
例 试证明任意给定的52个整数，它们之间必有两个
数，其和或差是100的倍数
证明：
设
为这52个整数的集合，
记
,则
构成了51个抽屉，
从而存在一个抽屉
，使得
设
则
除以100，其余数要么相同，要么其和为100。
如果余数相同，则这两数之差是100的倍数；
如果余数其和为100，则这两数之和是100的倍数。
41 抽屉原理的简单形式
饶戎轻吼荚容昧变脊做攒愤肺痢饯岁蜜危窥罚绘白吻戴锌再毗庚辐开汗幕5-抽屉原理5-抽屉原理
例 有n位代表参加会议，若每位代表至少认识另外
一个代表，则会议至少有两人认识的人数相同。
证明：
设某位代表认识的人数为
个，则
（视为n-1个抽屉），
而会议上有n个代表，故每位代表
认识的人数共有n个数（视为n个物品），
那么由基本定理，结论成立。
41 抽屉原理的简单形式
绎扼恰矫产税荣蚤狙发穿瓜狸阉篇希瑰迢焊届籽抛激矩佰玩蚕蛾寝码扼悬5-抽屉原理5-抽屉原理