ChCounting离散数学英文实用PPT课件.pptx

The Pigeonhole Principle
1
Pigeonhole Principle: Let k and n be positive integers (n > k), and we divide n balls among k boxes, then at least one box contains 2 balls
13 Pigeons, 12 Boxes
第1页/共33页
Generalized Pigeonhole Principle
Theorem: If we have n > k balls, k and n are positive integers, and we divide them among k boxes, then at least one box contains n/k balls
Assume 10 boxes (k = 10). Number of balls n = 11 ~ 20, at least a box has 2 ballsNumber of balls n = 21 ~ 30, at least a box has 3 ballsNumber of balls n = 31 ~ 40, at least a box has 4 balls…
Example: In a group of 1,000 people there are at least 3 people who have their birthday on the same day. Why?
This is because 1000/365 = 3
2
第2页/共33页
Generalized Pigeonhole Principle
Proof of the Generalized Pigeonhole Theorem:
By contradiction: Assume none of the k boxes contains n/k balls. Then, each box contains at most n/k – 1 balls. So, n  k(n/k – 1). We know n/k < n/k +1 (from the property: x < x + 1). So, n  k(n/k – 1) < k(n/k + 1 – 1) = n. Or, n < n. Contradiction!
3
第3页/共33页
Pigeonhole Principle Example
We have 5 possible grades: A, B, C, D, and F. How many students do we need to have to be sure at least 6 students get the same grade?
Boxes = grades = 5. Balls = students = n. Try to fill the boxes evenly: If we have 25 students, then we can evenly have 5 A’s, 5 B’s etc. So if we have 26 students, we need add a student to a grade which then has 6 students
Formally, n/5  6. So, n  26
4
第4页/共33页
Pigeonhole Principle Example
For every positive integer n, there is an integer m that is a multiple of n, and m consists of only the decimal digits of 0’s and 1’s
To show this, we construct m from n + 1 numbers: 1, 11, 111, 1111, …, 11…11 (n+1 1’s)
Divide each by n and find the two numbers (a and b) that are congruent (mod n) (same remainders) by Pigeonhole Principle (how?)
Then n | a – b ( assume a > b). Definition of congruence.
Let m = a – b. m is a multi