组合数学[第5版](英文版)第3章答案VIP免费

Math 475Text: Brualdi, Introductory Combinatorics 5th Ed.Prof: Paul TerwilligerSelected solutions for Chapter 31. For 1 ≤ k ≤ 22 we show that there exists a succession of consecutive days during whichthe grandmaster plays exactly k games. For 1 ≤ i ≤ 77 let bi denote the number of gamesplayed on day i. Consider the numbers {b1 + b2 + · · · + bi + k}76i= 0 ∪ {b1 + b2 + · · · + bj}77j= 1.There are 154 numbers in the list, all among 1, 2, . . . , 1 5 3 .T h e r e f o r et h enumbers {b1 + b2 +· · · + bi + k}76i= 0 ∪ {b1 + b2 + · · · + bj}77j= 1. are not distinct. Therefore there exist integers i, j(0 ≤ i < j ≤ 77) such that bi+1 + · · · + bj = k. During the days i + 1, . . . , j t h eg r a n d m a s t e rplays exactly k games.2. Let S denote a set of 100 integers chosen from 1, 2, . . . , 2 0 0such that i does not dividej for all distinct i, j ∈ S. We show that i ∈ S for 1 ≤ i ≤ 15. Certainly 1 ∈ S since1 divides every integer. By construction the odd parts of the elements in S are mutuallydistinct and at most 199. There are 100 numbers in the list 1, 3, 5, . . . , 1 9 9 .T h e r e f o r eeach of1, 3, 5, . . . , 1 9 9i st h eodd part of an element of S. We have 3 × 5 × 13 = 195 ∈ S. Thereforenone of 3, 5, 13, 15 are in S. We have 33 × 7 = 189 ∈ S. Therefore neither of 7, 9 is in S. Wehave 11× 17 = 187 ∈ S. Therefore 11 ∈ S. We have shown that none of 1, 3, 5, 7, 9, 11, 13, 15is in S. We show neither of 6, 14 is in S. Recall 33 × 7 = 189 ∈ S. Therefore 32 × 7 = 63 ∈ S.Therefore 2× 32× 7 = 126 ∈ S. Therefore 2× 3 = 6 ∈ S and 2× 7 =...