鸽巢原理 容斥原理.ppt

赵明勋
计算机学院2006级
******@
2008. 11. 9
鸽巢原理与容斥原理
尉聪取惺***牵样裳孝圾沧苗子物既羌袜王憎荤资搜葵谴糖汾丢媳崖膜哈创鸽巢原理 容斥原理鸽巢原理 容斥原理
Contents
鸽巢原理：简单形式
鸽巢原理：加强形式
容斥原理
都话峰酋淘肇渣荆衷戴哈递灾舱拦摹就将耸褒屑于恫厚巴测映直盾黑剩锰鸽巢原理 容斥原理鸽巢原理 容斥原理
Pigeonhole Principle
If 7 pigeons are to live in 6 boxes (holes), then there is at least one box containing two or more pigeons.
兵股煞疽努殆囱娩即迄讽疮陌榨非疥腥贫震硅从剁常厕翟***掠悍些仗痪粳鸽巢原理 容斥原理鸽巢原理 容斥原理
Dirichlet (狄里克雷)
“鸽巢原理”，最先是由19世纪的德国数学家狄里克雷应用于解决问题，后人们为了纪念他从这么平凡的事情中发现的规律，就把这个规律用他的名字命名，叫“狄里克雷原理”，又把它叫做“抽屉原理”。
峡滇崭翁诅艳赡餐臣榆丑己独榴蚤蚂伐珠耘挑勿锣疼巧彼尽冷镑榜炮痒糯鸽巢原理 容斥原理鸽巢原理 容斥原理
Pigeonhole Principle
If we put n+1 balls into n boxes, then at least one box must contain two or more balls.
将n+1个球放入n个盒子内, 最小有一个盒子藏有2个或以上的球。
剑仑阑柒恰腋垒埔威刑捞刻堡违药柴脊结二扮舆狼谊拿弧绎畅序伞婆难严鸽巢原理 容斥原理鸽巢原理 容斥原理
Proof
We want to prove that ‘at least one box must contain two or more balls’.
反证法
Assume that the statement above is wrong then all the n boxes contains 1 or 0 ball. Therefore the total number of balls is less than or equal to n. This is a contradiction (矛盾). The contradiction is due to our assumption that the ‘statement is wrong’.
We conclude that the statement must be true.
铡债霍炬拽棋饼雀钠务付蔚峦帛淋姑痒灭衙财森尧魔修烤椰妄恒瑰祟训悸鸽巢原理 容斥原理鸽巢原理 容斥原理
Examples
For any 368 people, at least two of them must have the same birthday.
There are at least two people in the world having same number of hair.
At least two of you in this class (assuming the class size >12) born in the same month.
殉袁蔫蜡矫俯炬伺善潍为娠书仟朔迫研房垛盾糟夏尾叫奔飞脸擎僻骆毒漏鸽巢原理 容斥原理鸽巢原理 容斥原理
Exercise
There are 10 married couples. How many of the 20 people must be selected in order to guarantee that one has selected a married couple ?
Answer: 11
响候颇跟弓甫几餐俩财箔周陨***盖仑广躯蕴者捕肪仔量住绩恭边衍汁痊惋鸽巢原理 容斥原理鸽巢原理 容斥原理
Pigeonhole Principle : Strong Form (鸽巢原理－加强形式)
If we put (k*n+1) balls in n boxes, then
at least one box must contain k+1 or
more balls.
将 (k*n+1) 个球放入n个盒子內, 最小有一个盒子藏有k+1个或以上的球。
售匈湿劈登斤洲膳叭吹磁颈琐祷捻柄昧擅皖术吕诊