《离散数学》杨争锋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:
令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 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.

解: 令aj是在这个月的第j天或第j天之前所打

的场数,则a1,a2,…,a30是不同正整数的一个 递增序列,其中1≤aj≤45。从而a1+14, a2+14, …, a30+14也是不同的正整数的一个 递增序列,其中15≤aj+14≤59。 60个正整数 a1, a2, … , a30, a1+14, a2+14, … , a30+14全都小于或等于59 。因 此,由鸽笼原理有两个正整数相等。因为aj (j=1,2,…,30)都不相同,并且aj+14 (j=1,2,…,30)也不相同,一定存在下标i和j 满足ai=aj+14。这意味着从第j+1天到第i天 恰好打了14场比赛。

(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.

解:把n+1整数a1, a2, …, an中的每一个都写成2 的幂与一个奇数的乘积。换句话说,令 aj=2kjqj, j=1,2,..,n+1, 其中kj是非负整数,qj是 奇数。整数q1, q2, …, qn+1都是小于2n的正整 数。因为只存在n个小于2n个正奇数,由鸽笼 原理,q1, q2, …, qn+1中必有两个相等。于是, 存在整数i和j使得qi=qj。令qi与qj的公共值是q, 那么ai=2kiq, aj=2kjq。因而,若ki<kj,则ai整 除aj;若ki>kj,则aj整除ai。

(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.

解:令a1, a2, …an2+1是n2+1个不同实数的序 列。与序列中的每一项ak联系着一个有序 对,即(ik,dk),其中ik是从ak开始的最长的 递增子序列的长度,且dk是从ak开始的最 长的递减子序列的长度。 假定没有长为n+1的递增子序列或递减子 序列。那么ik和dk都是小于或等于n的正整 数, k=1,2,…,n2+1。因此,有乘法规则,关 于(ik,dk)存在n2个可能的有序对。根据鸽笼 原理,n2+1个有序对中必有两个相等。换 句话说,存在as 和at, s<t, 使得is=it和ds=dt。 我们将证明这是不可能的。由于序列的项 是不同的,不是as<at就是as>at。

如果as<at,那么由于is=it,那么把as加到从at 开始的递增子序列前面就构造出一个从as 开始的长为is+1的递增子序列。从而产生矛 盾。 类似地,如果as>at,可以证明ds一定大于dt, 从而产生矛盾。

(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.

解:令A是6个人中的一人,组里的其他5个 人中至少有3个人是A的朋友,或至少有3个 人是A的敌人。这可以从推广的鸽笼原理得 出,因为当5个物体被分成两个集合时,其 中的一个集合至少有┌ 5/2 ┐=3个元素。 若是前一种情况,假定B,C和D是A的朋 友。如果这3个人中有2个人也是朋友,那 么这2个人和A构成彼此是朋友的3人组。否 则,B,C和D构成彼此为敌人的3人组。 对于后一种情况的证明,当A存在3个或 更多的敌人时,可以用类似的方法处理。

(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)


相关文档

《离散数学》杨争锋ch04-4
《离散数学》杨争锋ch02-4
《离散数学》杨争锋ch06-2
《离散数学》杨争锋ch04-3
《离散数学》杨争锋ch06-4
《离散数学》杨争锋ch07-4
《离散数学》杨争锋ch04-1
《离散数学》杨争锋ch01-2
《离散数学》杨争锋ch01-4
《离散数学》杨争锋ch07-1
电脑版