《离散数学》ch(16).ppt

§ The Pigeonhole Principle
Introduction
(1) The Pigeonhole Principle (page 313)
If k+1 or more objects are related into k boxes, then there is at least one box containing two or more of the objects.
Proof: 用反证法
See book.
整理课件
(2) Examples
(a) Example 1 (page 313)
Among any group of 367 people, there must be at least two with the same birthday, because there are only 366 possible birthdays.
(b) Example 2 (page 313)
In any group of 27 English words, there must be at least two that begin with the same letter, since there are 26 letters in the English alphabet.
整理课件
(c) Example 3 (page 313)
How many students must be in a class to guarantee that at least two students receive the same score on the final exam, if the exam is graded on a scale from 0 to 100 points.
Solution:
102
整理课件
(d) Example 4 (page 314)
Show that for every integer n there is a multiple of n that has only 0s and 1s in its decimal expansion.
Solution:
令n是一个正整数,考虑n+1个整数
1, 11, ……, 111…1(最终一个整数有n+1个1)
由于一个整数被n除后,将有n种可能的余数,所以上述n+1个正整数中有2个,它们被n除后余数一样,即:这两个正整数相减后,仅有如干个0和如干个1构成,且能被n整除.
整理课件
2. The Generalized (广义) Pigeonhole Principle
(1) The Generalized Pigeonhole Principle
If N objects are placed into k boxes, then there is at least one box containing at least ┌ N / k ┐objects.
Proof: 用反证法
See book.
整理课件
(2) The Minimal Number of Objects.
-----so that at least r of these objects must be in one of k boxes when these objects are distributed among the boxes.
Solution:
┌ N/k ┐>=r
The smallest integer N with N/k>r-1,
namely,
N=k(r-1)+1
整理课件
(3) Examples
(a) Example 5 (page 315)
Among 100 people there are at least ┌ 100/12 ┐=9 who were born in the same month.
整理课件
(b) What is the minimum number of students required in a discrete mathematics class to be sure that at lea