鴿巢原理 容斥原理

1、2006級(jí)2008. 11. 9鴿巢原理與容斥原理1Contents鴿巢原理：簡(jiǎn)單形式鴿巢原理：加強(qiáng)形式容斥原理2Pigeonhole PrincipleIf 7 pigeons are to live in 6 boxes (holes), then there is at least one box containing two or more pigeons.3Dirichlet (狄里克雷)“鴿巢原理”，最先是由19世紀(jì)的德國(guó)數(shù)學(xué)家狄里克雷應(yīng)用于解決問(wèn)題，后人們?yōu)榱思o(jì)念他從這么平凡的事情中發(fā)現(xiàn)的規(guī)律，就把這個(gè)規(guī)律用他的名字命名，叫“狄里克雷原理”，又把它叫做“抽屜原理”。4Pigeon

2、hole Principle If we put n+1 balls into n boxes, then at least one box must contain two or more balls. 將n+1個(gè)球放入n個(gè)盒子內(nèi), 最小有一個(gè)盒子藏有2個(gè)或以上的球。5ProofWe 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. Th

3、erefore 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.6Examples For any 368 people, at least two of them must have the same birthday.There are at l

4、east 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. 7Exercise 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: 118

5、Pigeonhole Principle : Strong Form (鴿巢原理加強(qiáng)形式)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) 個(gè)球放入n個(gè)盒子內(nèi), 最小有一個(gè)盒子藏有k+1個(gè)或以上的球。9ProofWe want to prove that at least one box must contain k+1 or more balls.Assume that the statement above is wrong then all

6、the n boxes contains k or less balls. Therefore the total number of balls is less than or equal to n*k. This is a contradiction (矛盾). The contradiction is due to the assumption that the statement is wrong.We conclude that the statement must be true.10Exercise There are 90 people in a hall. Some of t

7、hem know each other, some are not. Prove that there are at least two persons in the hall who know the same number of people in the hall.What should be the holes and pigeons? How many holes are there?11Solution If there is a person in the hall who does not know any other people, then each of the othe

8、r persons in the hall may know either 0, or 1, or 2, or 3, . , or 88 people. Therefore we have 89 holes numbered 0, 1, 2, 3, . , 88, and have to distribute among 90 people.Next, assume that every person in the hall know at least one other person. Again, we have 89 holes 1, 2, 3, . , 89 and 90 people

9、.In either case, we can apply the Pigeonhole Principle to get the conclusion.12Pigeonhole Principle : Strong Form (鴿巢原理加強(qiáng)形式)令q1, q2, , qn為正整數(shù)。 如果將 q1 + q2 + qn n + 1個(gè)物體放入n個(gè)盒子內(nèi)，那么， 或者第一個(gè)盒子至少含有q1個(gè)物體，或者第二個(gè)盒子至少含有q2個(gè)物體，, 或者第n個(gè)盒子至少含有qn個(gè)物體。13Pigeonhole Principle : Strong Form (鴿巢原理加強(qiáng)形式)證明：（反證法）設(shè)將q1 + q2 + qn n + 1個(gè)物體分到n個(gè)盒子中。 如果對(duì)于每個(gè)i=1, 2, , n, 第i個(gè)盒子含有少于qi個(gè)物體， 那么所有盒子中的物體總數(shù)不超過(guò)(q1-1) + (q2-1) + (qn-1) = q1 + q2 + qn n該數(shù)比所分發(fā)的物體總數(shù)少1， 因此我們斷言， 對(duì)于某一個(gè)i=1, 2, , n, 第i個(gè)盒子至少包含 qi個(gè)物體。14Pigeonhole Principle : Strong Form (鴿巢原理加強(qiáng)形式)將m個(gè)物體放入n個(gè)盒子內(nèi)