# 《离散数学》杨争锋ch04-2_图文

§4.2 The Pigeonhole Principle 1. 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:

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 least six will receive the same grade, if there are five grades, A, B, C, D, and F? Solution: N=k(r-1)+1 =5*(6-1)+1 =26

(c) Example 7 (i) How many cards must be selected from a standard deck (纸牌) of 52 cards to guarantee that at least three cards of the same suit are chosen? Solution: N=k(r-1)+1 =4*(3-1)+1 =9

(ii) How many must be selected to guarantee that at least three hearts are selected? Solution: Note that in the worst case, we can select all the clubs, diamonds, and spades, 39 cards in all, before we select a single heart. The next three cards will be all hearts, so we may need to select 42 cards to get three hearts.

(d) Example 8 and 9 (page 315~316) Please read them by yourself.

3. Some Elegant Applications of the Pigeonhole Principle (1) Example 10 (page 316) During a month with 30 days a baseball team plays at least one game a day, but no more than 45 games. Show that there must be a period of some number of consecutive days during which the team must play exactly 14 games.

(2) Example 11 (page 317) Show that among any n+1 positive integers not exceeding 2n there must be an integer that divides one of the other integers. Solution: See next slide.

(3) Strictly Increasing (or Decreasing) Subsequence of a Sequence Example 12 (page 317) The sequence 8,11,9,1,4,6,12,10,5,7 contains ten terms. Note that 10=32+1. There are four increasing subsequences of length four, namely, 1,4,6,12; 1,4,6,7; 1,4,6,10; and 1,4,5,7. There is also a decreasing subsequence of length four, namely, 11,9,6,5.

(4) Theorem 3 (page 317) Every sequence of n2+1 distinct real numbers contains a subsequence of length n+1 that is either strictly increasing or strictly decreasing. Proof: See next slide.

(5) Ransey number R(m,n) (a) Example 13 (page 318) Assume that in a group of six people, each pair of individual consists of two friends or two enemies. Show that there are either three mutual (相互的) friends or three mutual enemies in the group. Solution: See next slide.

(b) Ramsey number R(m,n) Assume m and n are positive integers greater than or equal to 2 R(m,n)--------the minimum number of people at a party so that there are m mutual friends or n mutual enemies (Assume every pair of people at the party are friends or enemies.) (c) How to calculate R(m,n)? (Difficult!!!) R(3,3)=6 (from Example 13 and exercise 24)