习题讲解1-4.pdf

第一次作业 第一次作业 1 Show that if n 1 integers are chosen from the set 1 2 3n then there are always two which differ by 1 or 2 2 Prove that for any n 1 integers a1 a2 an 1 there exist two of the integers ai and aj with i j such that ai aj is divisible by n 3 Generalize application 5 by choosing how many integers from the set 1 2 2n 1 Show that if n 1 integers are chosen from the set 1 2 3n then there are always two which differ by 1 or 2 注 参考从注 参考从 1 2 3n 里选择里选择 n 个整数 必然存在两个数相差为个整数 必然存在两个数相差为 1 的情况 出的情况 出 发点发点要从鸽巢原理着手 要从鸽巢原理着手 Answer Considering the n groups 1 2 3 4 5 6 3n 2 3n 1 3n While we choose n 1 elements from the n groups According to pigeonhole principle there will be at least two elements which come from the same group and they differ by 1 or 2 2 Prove that for any n 1 integers there exist two of the integer and with i such that is divisible by n 注 出发点从差可被注 出发点从差可被 n 整除 说明对整除 说明对 n 取余 余数相同取余 余数相同 Answer For the n 1 integers each one of them can be written in the form ri is the corresponding remainder ai pi n ri Where ri 0 1 n 1 So according to pigeonhole principle there will be two elements ai and aj which have the same reminder value ri rj Then we can get that ai aj pi n ri pj n rj pi pj n So there exist two of the integers ai and aj with i j such that ai aj is divisible by n 3 Generalize Application 5 by choosing how many integers from the set 1 2 2n Application 5 From the integer 1 200 we choose 101 integers Show that among the integers chosen there are two such that one of them is divisible by other Answer We know that any integer can be written in the form 2k a where k 0 and a is odd thus for any element xi in set 1 2 2n can be written as xi 2ki ai For the set 1 2 3 2n it needs n different ai whose value is equals to one element in the set 1 3 5 2n 1 According to pigeonhole principle we should choose n 1 integers from the set while there are at least two elements xiand yj have the same reminders that ai is equal to aj xi 2ki ai yj 2kj aj ai aj and we have xi yj 2ki 2kj 2ki kj So there are two elements such that one is divisible by the other in the set 注意 这个 1 2n 不是任意 2n 个数 选择 n 1 个可以保证成立 但是怎么确 定 n 1 个是最小的呢 鸽巢原理 第二次作业 第二次作业 Third Edition 4 a 8 18 31 Fifth Edition 4 a 9 19 38 61 Consider an 9 by 9 board and 9 rooks of which 5 are red and 4 are blue Suppose you place the rooks on the board in non attacking positions at random What is the probability that the red rooks are in rows 1 3 5 7 9 What is the probability that the red rooks are both in rows 1 2 3 4 5 and in columns 1 2 3 4 5 1 How many distinct positive divisors do each of the following numbers have a 34 52 76 11 Answer In this question we can see that the numbers 3 5 7 and 11 are prime numbers By the fundamental theorem of arithmetic each factor is of the form 34 52 76 11 Where 0 i 4 0 j 2 0 k 6 0 l 1 So there are 5 choices of i 3 for j 7 for k and 2 for l By the multiplication principle the numbers of factors is 5 3 7 2 210 2 In how many ways can 15 people be seated at a round table if B refuses to sit next to A What if B only refuses to sit on A s right Answer Theorem 3 2 2 58 页 集合排列 1 If B refuses to sit next to A There are 14 ways that 15 people can be seated at a round table If we view A and B as one people group with A2 2 permutations then there are A2 2 13 ways that 14 people can be seated at a round table So the number of ways that 15 people can be seated at a round table with B not adjacent to A is 14 A2 2 13 2 If B only refuses to sit on A s right There are 14 ways that 15 people can be seated at a round table If we view A and B as one people group with 1 permutations while B only refuses to sit on A s right then there are 1 13 ways that 14 people can be seated at a round table So the number of ways that 15 people can be seated at a round table with B not adjacent to A is 14 13 3 We are given 8 rooks 5 of which are red and 3 of which are blue a In how many ways can the 8 rooks be placed on an 8 by 8 chessboard so that no two can attack another b In how many ways can the 8 rooks be placed on a 12 by 12 chessboard so that no two rooks attack each other Answer a By the Theorem 3 4 3 69 页 the number of ways to arrange these rooks on an 8 by 8 board so that no two rooks can attack one another equals 8 8 5 3 b First we choose 8 rows of the 12 rows the number is 12 8 Second we also choose 8 columns of the 12columns the number is 12 8 Then By the Theorem 3 4 3 69 页 the number of ways to arrange these rooks on an 12 by 12 board so that no two rooks can attack one another equals 12 8 12 8 8 8 5 3 4 How many integral solutions of x1 x2 x3 x4 x5 30 satisfy x1 2 x2 0 x3 5 and x4 8 Answer Theorem 3 5 1 71 页 Example 74 页 多重集组合 Introduce new variables y1 x1 2 y2 x2 y3 x3 5 y4 x4 8 The equation becomes y1 y2 y3 y4 25 y1 0 y2 0 y3 0 y4 0 The lower bounds on the xi s are satisfied if and only if the yi s are non negative The number of non negative integral solutions of the new equation is 25 4 1 25 28 25 5 PPT Consider a 9 by 9 board and 9 rooks of which 5 are red and 4 are blue Suppose you place the rooks on the board in non attacking positions at random What is the probability that the red rooks are in rows 1 3 5 7 9 What is the probability that the red rooks are both in rows 1 2 3 4 5 and in columns 1 2 3 4 5 Answer 综合题 排列组合 要理解非攻击车的方法的实际含义 By the Theorem 3 4 3 69 页 the number of ways to arrange 5 red rooks and 4 blue rooks on an 9 by 9 board so that no two rooks can attack one another equals 9 9 5 4 1 If all the 5 red rooks are placed on row 1 3 5 7 9 we should choose 5 columns from all the 9 columns for those 5 red rooks Then the red rooks are placed on a 5 by 5 determined board And the rest 4 blue rooks are placed on the rest 4 by 4 board So the number of all the possible combinations which ensure that the red rooks are in rows 1 3 5 7 9 is 9 5 5 4 or 9 5 5 4 4 9 Then p1 9 5 5 4 9 9 5 4 5 4 9 2 5 red rooks are on a 5 by 5 chessboard and the rest 4 blue rooks are on a 4 by 4 chessboard from 9 by 9 chessboard So the number of all the possible combinations which ensure that the red rooks are both in rows 1 2 3 4 5 and in columns 1 2 3 4 5 is y 5 4 Then p1 5 4 9 9 5 4 5 4 9 2 第三次作业 第三次作业 6 a Determine the inversion sequence of the following permutation of 1 2 8 35168274 7 a Construct the permutation of 1 2 8 whose inversion sequence is 2 5 5 0 2 1 1 0 15 b For each of the following combinations of x7 x6 x1 x0 determine the combination that immediately follows it by using the base 2 arithmetic generating scheme x7 x5 x3 29 1 Determine the 7 subset of 1 2 10 that immediately follows 1 2 4 6 8 14 15 in the lexicographic order 2 Then determine the 7 subset that immediately precedes 1 2 4 6 8 14 15 33 In which position dose the combination 2489 occur in the lexicographic order of the 4 combinations of 1 2 3 4 5 6 7 8 9 6 a Determine the inversion sequence of the following permutation of 1 2 8 35168274 Answer In sequence 35168274 There are 2 integers which precede 1 but greater than 1 Similarly There are 4 integers which precede 2 but greater than 2 There are 0 integers which precede 3 but greater than 3 There are 4 integers which precede 4 but greater than 4 There are 0 integers which precede 5 but greater than 5 There are 0 integers which precede 6 but greater than 6 There are 1 integers which precede 7 but greater than 7 There are 0 integers which precede 8 but greater than 8 So the inversion sequence of 35168274 is 2 4 0 4 0 0 1 0 7 b Construct the permutation of 1 2 8 whose inversion sequence is 2 5 5 0 2 1 1 0 Answer We begin with 8 empty locations which we label 1 2 8 from left to right Use algorithm 2 to solve this problem 1 1 2 1 2 3 1 2 3 4 4 1 2 3 5 4 1 5 2 3 6 4 1 6 5 2 3 7 4 1 6 5 7 2 3 8 4 8 1 6 5 7 2 3 So the permutation whose inversion sequence is 2 5 5 0 2 1 1 0 is 48165723 15 b For each of the following combinations of x7 x6 x1 x0 determine the combination that immediately follows it by using the base 2 arithmetic generating scheme x7 x5 x3 Answer The combination x7 x5 x3 corresponds to the binary numeral 10101000 10101000 1 10101001 So the combination that immediately follows x7 x5 x3 is x7 x5 x3 x0 29 1 Determine the 7 subset of 1 2 15 that immediately follows 1 2 4 6 8 14 15 in the lexicographic order Answer Consider the 7 subset a1a2a3a4a5a6a7 1 2 4 6 8 14 15 of 1 2 15 For k 5 ak 8 15 and ak 1 9 is the largest integer different from 1 2 4 6 8 14 15 Then the r combination which is the immediately successor of a1a2a3a4a5a6a7 in the lexicographic ordering is a1 a5 1 a5 2 a5 7 5 1 1 2 4 6 9 10 11 2 Then determine the 7 subset that immediately precedes 1 2 4 6 8 14 15 Answer For k 6 ak 14 15 and ak 1 13 is different from 1 2 4 6 8 14 15 Then the r combination which is the immediately precedes of a1a2 a6 in the lexicographic ordering is a1a2 a6 1 a7 1 2 4 6 8 13 15 33 In which position dose the combination 2489 occur in the lexicographic order of the 4 combinations of 1 2 3 4 5 6 7 8 9 Answer Theorem 4 4 2 The r combination a1a2a3 ar of 1 2 n occurs in place number C n r C n a1 r C n a2 r 1 C n ar 1 2 C n ar 1 in the lexicographic order of the r combinations of 1 2 n We apply Theorem 4 4 2 and find that 2489 is in place C 9 4 C 7 4 C 5 3 C 1 2 C 0 1 126 35 10 0 0 81 Theorem4 4 2 P112 the r combination a1a2 ar of 1 2 n occurs in place number C n r C n a1 r C n a2 r 1 C n ar 1 2 C n ar 1 In the lexicographic order of the r combinations of 1 2 n 第四次作业 1 Find the number of integers between 1 and 10000 inclusive which are not divisible by 4 5 or 6 8 Determine the number solutions of the equation x1 x2 x3 x4 14 in positive integers x1 x2 x3 x4 not exceeding 8 14 Determine the general formula for the number of permutations of the set 1 2 n in which exactly k integers are in their natural positions 25 Count the permutations i1 i2 i3 i4 i5 i6 of 1 2 3 4 5 6 where i1 1 5 i3 2 3 5 i4 4 and i6 5 6 29 How many circulars permutations are there of the multiset 3 a 4 b 2 c 1 d where for each type of letter all letters of that type do not appear consecutively 1 Find the number of integers between 1 and 10000 inclusive which are not divisible by 4 5 or 6 Answer Let P1 be the property that an integer is divisible by 4 P2 the property that an integer is divisible by5 and P3 the property that an integer is divisible by 6 Let S be the set consisting of the 10000 positive integers For i 1 2 3 let Ai be the set consisting of the those integers in S with property Pi We wish to find the number of integers in A 1 A 2 A 3 We first see that A1 10000 4 2500 A2 1000 5 2000 A3 10000 6 1666 Integers in the set A1 A2 are divisible by both 5 and 6 But an integer is divisible by both 5 and 6 if and only if it is divisible by lcm 4 5 Since lcm 4 5 20 lcm 5 6 30 and lcm 4 6 12 we see that A1 A2 10000 20 500 A1 A3 10000 30 333 A2 A3 10000 12 833 Because lcm 4 5 6 60 we conclude that A1 A2 A3 10000 60 166 Thus by the inclusion exclusion principle the number of integers between 1 and 10000 that are divisible by none of 4 5 6 equals A 1 A 2 A 3 10000 2500 2000 1666 500 333 833 166 5334 2 Determine the number solutions of the equation x1 x2 x3 x4 14 in non negative integers x1 x2 x3 x4 not exceeding 8 注意看好题 一个是非负 一个是正整数 注意看好题 一个是非负 一个是正整数 且且两个两个题题变量个数是不同的 变量个数是不同的 Answer Let S be the set of all non negative integral solutions of the above equation The size of S is S 14 4 1 14 17 14 680 Theorem 3 5 1 中 公式 r kr1 Let pi be the property that xi 9 i 1 2 3 4 Let Ai denote the subset of S consisting of the solutions satisfying property pi Applying the inclusion exclusion principle we have A 1 A2 A3 A4 5 4 1 5 56 A1为x1 x2 x3 x4 14的整数解集合 满足x1 9 x2 0 x3 0 x4 0 A1 A2 A1 A3 A1 A4 A2 A3 A2 A4 A3 A4 0 A 1 A2 A3 A1 A2 A4 A1 A3 A4 A2 A3 A4 0 A 1 A2 A3 A4 0 A 1 A2 A3 A4 680 56 4 456 3 Determine a general formula for the number of permutations of the set 1 2 n in which exactly k integers are in their natural positions Answer Theorem 6 3 1 173 页 错位排序 There are exactly k integers in their natural positions so n k integers are just not in their natural positions And we have n k choices to choose k integers from the set 1 2 n The general formula for it is n k Dn k 4 Count the permutations i1 i2 i3 i4 i5 i6 of 1 2 3 4 5 6 where i1 1 5 i3 2 3 5 i4 4 and i6 5 6 Answer Determine the number of ways to place 6 non attacking rook