Mathematical thinking problem solving and proofs solution manual 2

63 Part II Solutions Chapter 5: Combinatorial Reasoning 64 SOLUTIONS FOR PART II 5. COMBINATORIAL REASONING 5.1. When rolling n dice, the probability is 1/2 that the sum of the numbers obtained is even. There are 6n equally likely outcomes; we show that in half of them the sum is even. For each of the 6n−1 ways to roll the first n − 1 dice, there are six ways to roll the last die, and exactly three of them produce an even total. Thus there are 6n/2 ways to roll an even sum. 5.2. Probabilities for the sum of two rolled dice. k 2 3 4 5 6 7 8 9 10 11 12 probability 136 2 36 3 36 4 36 5 36 6 36 5 36 4 36 3 36 2 36 1 36 5.3. The numbers x and 14 − x are equally likely to be the sum of the num- bers facing up on two dice. Whenever i, j are two dice rolls that sum to x , the numbers 7 − i and 7 − j are two dice rolls that sum to 14 − x , since 1 ≤ i ≤ 6 implies that 1 ≤ 7− i ≤ 6. Furthermore, the transformation is its own inverse. This establishes a bijection between the set of (ordered pair) dice rolls summing to x and the set of (ordered pair) dice rolls summing to 14 − x , so the two sets are equally likely when the individual ordered pairs are equally likely rolls. 5.4. There are ml words of length l from an alphabet of size m, and in∏l i=1(l + 1 − i) of them each letter is used at most once. For each position in the word, a letter must be chosen. When repetitions are allowed, there are m choices at each of the l positions, regardless of earlier choices. When repetitions are forbidden, the number of ways to fill the ith position is l + 1 − i , regardless of how the earlier positions were filled. In each case, multiplying these factors counts the arrangements, by the product rule. 5.5. Given n married couples, there are n(n − 1) ways to form pairs con- sisting of one man and one woman who are not married to each other. We must choose one person of each type. Whichever type we choose first, we can choose such a person in n ways. Whichever person we choose, there are n − 1 person of the opposite sex other than that person’s spouse, and we choose one of those. 5.6. There are n! bijections from an n-element set A to an n-element set B. List the elements of A in some order, as {a1, . . . , an}. The bijection assigns an element of B to each element of A. Furthermore, the assigned elements are distinct. The image of a1 can be chosen in n ways. For each way to choose this, there are n − 1 ways to choose the image of a2. In general, for each way to choose the images of a1, . . . , ai , there are n − i ways to choose the image of ai+1. By the product rule, the number of ways to form a bijection is ∏n−1 i=0 (n − i). 5.7. There are 12 · 47 + 1 · 48 ways to pick two cards from a standard 52- card deck such that the first card is a spade and the second card is not an Ace. There are 13 ways to start with a spade. If the spade is not the Ace, then there are 47 ways to pick the second card, since one non-Ace has been used. If the spade is the Ace, then there are 48 ways to pick the second card. Combining the two cases yields the answer 12 · 47 + 48 Alternatively, one can name a spade for the first card and a non-Ace for the second card, eliminating the cases where the same card is named twice. This yields 13 · 48 − 12, which equals the value above. 5.8. The coefficient of x4 y5 in the expansion of (x +y)9 is (94), by the Binomial Theorem. The value is 9·8·7·64·3·2·1 , which equals 126. 5.9. Probabilities in a 5-card hand. We divide the number of hands with the desired property by (52 5 ) , the total number of possible hands. a) Hands having at least three cards with the same rank. If we simply pick three cards of the same rank and then pick two other cards, we might get four of the same rank; such hands would be counted four times. Thus we count the two cases separately. By picking a rank and an extra card, there are 13 · 48 hands with four of a single rank. For the other case, we pick a rank, leave out one of that rank, and pick two cards of other ranks, in 13 · 4 · (482 ) ways. Thus the answer is 13 · 48(1 + 2 · 47)/(525 ). b) Hands having at least two cards with the same rank. To the numer- ator in part (a), we could add on the hands having two but not three from a single rank. Note that we must avoid double-counting the hands having a pair from each of two ranks. Alternatively, we can subtract from the total the hands having no pair of cards with the same rank. Since we pick five different ranks and one card from each, there are (13 5 ) 45 of these, and the answer is 1 − (135 )45/(525 ). Note that about half of the hands have no repeated ranks, since (13 5 ) 45/ (52 5 ) = 52·48·44·40·36 52·51·50·49·48 = .50708. 5.10. In 2n coin flips, the probability of obtaining exactly n heads is (2n n ) /22n. There are 22n lists of heads and tails, all equally likely. A list with n heads is determined by choosing locations for the n heads in the list. Thus (2n n ) outcomes have n heads. When n = 10, the value is (19 · 17 · 13 · 11)/218 after cancellation. This equals approximately .176197. 65 Part II Solutions Chapter 5: Combinatorial Reasoning 66 5.11. The most common difference between the rolls on two dice is 1. Note that specified unordered pairs of distinct numbers appear in two ways out of 36, while specified pairs of equal numbers appear in only one way. In- dexing the rows by the roll of the first die and the columns by the roll on the second die yield the following table of outcomes for the difference. Each position in the table has probability 1/36 of occurring. Collecting those with a particular difference into a single event shows that the differences 0,1,2,3,4,5 occur with probabilities 636 , 10 36 , 8 36 , 6 36 , 4 36 , 2 36 . 5.12. The probability that three rolls of a die sum to 11 is 1/8. When the first roll is 1, 2, 3, 4, 5, or 6, the numbers of ways to throw the other two to reach a total of 11 are 3, 4, 5, 6, 5, or 4, respectively. Since each ordered triple occurs with probability 1/63, the answer is thus 27/216. 5.13. The probabilities for the number of 6s in four rolls. When we obtain a 6 exactly k times, there are five choices each for the remaining 4 − k rolls. We pick the positions for the 6s in (4 k ) ways, and for each there are 54−k ways to complete the list. Thus the probability is (4 k ) 54−k/64. k 0 1 2 3 4 instances 625 500 150 20 1 probability .4823 .3858 .1157 .0154 .0008 5.14. Probability of sum n in three selections from [n] is (n −1)(n −2)/(2n3). There are n3 equally likely outcomes. The number of outcomes that sum to n is the number of solutions to x1 + x2 + x3 = n in positive integers. Proof 1 (selections with repetition). The number of solutions is the number of solutions to y1 + y2 + y3 = n − 3 in nonnegative integers. This equals the number of selections of n − 3 elements from three types with repetition allowed, which is (n−1 2 ) , by Theorem 5.31. Thus the probability is (n − 1)(n − 2)/(2n3). Proof 2 (summations). When x1 = i , there are n − i − 1 ways to assign the final two values, since x2 can then take any value from 1 to n − i − 1, which determines x3. Thus the number of solutions is ∑n−2 i=1 (n − i − 1). The summands are the integers from 1 to n − 2 (in reverse order), so the sum is (n − 1)(n − 2)/2. 5.15. The size of the union of k pairwise disjoint finite sets A1, . . . , Ak is the sum of their sizes. We use induction on k. Basis step: k = 1. The one set A1 is also the union, and its size is its size. Induction step: k > 1. Let B be the union of A1, . . . , Ak−1. By the induction hypothesis, |B| = ∑k−1i=1 Ai . Since Ak is disjoint from each of A1, . . . , Ak−1, also Ak ∩ B = ∅. Now Corollary 4.41 states that |Ak ∪ B| = |Ak | + |B|. Together, these yield ∣∣∣⋃ki=1 Ai ∣∣∣ = ∑ki=1 |Ai |. 5.16. The rule of product, from the rule of sum. In the set T , elements are formed in k steps. Each element of T can be expressed as a k-tuple in which the ith coordinate lists the way in which the ith step is performed. We are given that the ith step can be performed in ri ways, no matter how the earlier steps are performed. We use induction on k to prove that |T | = ∏ki=1 ri . Basis step: k = 1. The elements of T are the ways to perform the step, so |T | = r1. Induction step: k > 1. We partition T into sets, depending on how the first k − 1 steps are performed. The given condition implies that each set has size rk . The induction hypothesis implies that there are ∏k−1 i=1 ri sets in the partition. Since each has size rk , and the sets are pairwise disjoint, the rule of sum implies that |T | = ∏ki=1 ri . 5.17. The only solution of n! + m! = k! in positive integers is n = m = 1 and k = 2. Suppose that n!+ m! = k!; by symmetry, we may assume that n ≥ m. Since m! > 0, we have k! > n! ≥ m!. Using the definition of factorial, we divide the equation by n! to obtain 1 + m!/n! = k(k − 1) · · · (n + 1). Since 1 and k(k − 1) · · · (n + 1) are integers, m!/n! must be an integer. Since m ≤ n, this requires m = n. Now we have 2 = k(k − 1) · · · (n + 1). This requires n + 1 ≤ 2 and k = n + 1, leaving only the possibility (n, m, k) = (1, 1, 2). This possibility is indeed a solution. 5.18. Sets of six cards with at least one card in every suit. The distribu- tions over suits can be 3111 or 2211. In the first case, we pick the suit contributing three cards, pick the three cards, and pick one card from each of the others. In the second case, we pick the two suits contributing two cards, pick two cards from each, and pick one card each from the remain- ing two suits. In each case, the product rule applies to these choices. Thus the answer is (4 1 )(13 3 ) 133 + (42)(132 )2132. 5.19. Counting 6-digit numbers by the number of distinct digits. Let k be the number of distinct digits. There are 9 such natural numbers with k = 1 (six copies of the same digit). When k = 2, we pick the two digits and choose a sequence with these two digits, excluding the sequences with all of one type. Thus the answer is (10 2 ) (26 − 2) = 45 · 62 = 2790. When k = 6, we are arranging six elements from a set of size 10, so the count is 10 · 9 · 8 · 7 · 6 · 5 = 151200. When k = 5, we pick the one repeated digit, pick its two positions, and arrange four of the remaining digits in the remaining positions. The count is 10 (6 2 ) · 9 · 8 · 7 · 6 = 453600. 67 Part II Solutions Chapter 5: Combinatorial Reasoning 68 When k = 4, we might use three of one digit or two each of two digits. In the first case, counting as in the case k = 5 yields 10(63) · 9 · 8 · 7 = 100800. In the second case, we pick the two repeats, pick two positions for each, and arranging two other digits in the remaining positions to get(10 2 )(6 2 )(4 2 ) · 8 · 7 = 226800. Altogether we have 327600 numbers with k = 4. When k = 3, we can pick three numbers and form 6-tuples from that 3-set, subtracting the 6-tuples that don’t use all the numbers. For a given three, there are 3 + 3(26 − 2) bad 6-tuples. Thus the answer is (103 )[36 − 3 · 26 + 3] = 64800. As a check, 9 + 2790 + 64800 + 327600 + 453600 + 151200 = 999999. 5.20. (n5 − 5n3 + 4n)/120 is an integer whenever n is a positive integer. The numerator of this fraction factors as (n + 2)(n + 1)n(n − 1)(n − 2). For n ∈ {1, 2}, the value is 0. For n > 2, the numerator is the product of five consecutive natural numbers, so it suffices to show that the product of five consecutive natural numbers is divisible by 120. Proof 1 (combinatorial proof). The number (l +4)(l +3)(l +2)(l +1)l/5! is the number of ways to choose 5 items from a set of l + 4 distinct items. The more general statement that the product of any k consecutive positive integers is divisible by k! follows by the same argument. Proof 2 (divisibility). A number is divisible by 120 if and only if it is divisible by 5, by 3, and by 23. Thus it suffices to show that every product of five consecutive integers has these factors. Since the multiples of an integer t are spaced t apart, five consecutive integers contain exactly one number divisible by 5 and at least one divisible by 3. They also contain at least two numbers divisible by 2, and one of these is divisible by 4. Hence there are at least three powers of 2 in the product. Note that being divisible by 2 and by 4 does not imply that a number is divisible by 8. Proof 3 (induction and divisibility). We prove by induction on n that (n + 2)(n + 1)n(n − 1)(n − 2) is divisible by 120. The product is 0 when n = 1. For the induction step, suppose that the claim holds when n = m. To show that (m + 3)(m + 2)(m + 1)m(m − 1) is divisible by 120, we show that this minus (m + 2)(m + 1)m(m − 1)(m − 2) is divisible by 120. With the induction hypothesis, we conclude that the claim holds when n = m + 1. The desired difference simplifies to 5(m + 2)(m + 1)m(m − 1). Thus it suffices to show that the product of four consecutive integers is divisible by 24. We could apply a divisibility analysis (as in Proof 2) or prove this state- ment itself by induction. The induction step would reduce to the statement that the product of three consecutive integers is divisible by 6. We could prove this using divisibility or induction, reducing to the statement that the product of two consecutive integers is divisible by 2. If we ever switch to the divisibility approach, then we use an argument like Proof 2. The reduction to the next induction is always done in the same way. We can combine all the reductions into a single inductive proof (by induction on k + l) of the more general statement that the product of k consecutive natural numbers starting with l is divisible by k! (see Exercise 7.21.) 5.21. There are (m 2 )(n 2 ) rectangles of all sizes formed using segments in a grid with m horizontal lines and n vertical lines. Each such rectangle is determined, uniquely, by choosing two vertical lines and two horizontal lines as boundaries. 5.22. Every convex n-gon has (n 4 ) pairs of crossing diagonals. Proof 1 (bijection). The direct proof is that every crossing pair of di- agonals is determined by the four endpoints of the two diagonals, and this establishes a bijection from the set of crossing pairs of diagonals to the set of 4-tuples of vertices, since each 4-set of vertices can be matched up in exactly one way to produce a crossing pair of diagonals. Proof 2 (summations). We count the crossings involving diagonals from one vertex. Let the vertices be v1, . . . , vn in order. The diagonal from vn to vk is crossed by (k − 1)(n − k − 1) diagonals not involving vn. Thus∑n−1 k=1(k − 1)(n − k − 1) crossings involve vn. This argument is valid for each vertex, so we can sum over the vertices and divide by the number of times each crossing is counted to conclude that the total number of crossings is n 4 ∑n−1 k=1(k − 1)(n − k − 1). We need the sum∑n−1 k=1(k − 1)(n − k − 1) = (n 3 ) (also needed in an inductive proof). One can compute this by writing the summand as a polynomial and applying Propositions 4.7 and 4.16. Exer- cise 9.11 evaluates a more general sum by a combinatorial argument. 5.23. Multiplicities of poker hands. a) One pair (two cards of equal rank and no others of equal rank). This occurs in (13 1 )(4 2 )(12 3 ) 43 ways: pick the special rank, pick two cards from it, pick the three other ranks, pick one card each from those ranks. b) Full house (two cards of equal rank and three cards of another rank). This occurs in 13 ·12(42)(43) ways: pick the two ranks (order matters because the chosen ranks are distinguished by the number of cards they contribute), pick 2 cards from the first rank, pick three cards from the second rank. c) Straight flush (five cards in sequence from the same suit). A straight flush is determined by choosing a suit and choosing the rank where the 5- card sequence starts. There are four suits and 10 starting values (10 J Q K A is the highest), so there are 40 such hands. 69 Part II Solutions Chapter 5: Combinatorial Reasoning 70 5.24. Bridge distributions. The probability of each distibution is the num- ber of such hands divided by the total number of 13-card hands, (52 13 ) . For each distribution, we list the number of hands and the rank. To count the hands, we first assign the multiplicities to suits, then we choose the specified number of cards from each suit. The number of ways to assign the multiplicities depends on how many times each multiplicity occurs. With four distinct multiplicities, there are 24 ways to assign them to suits. When three numbers arise (one repeated), as in 5440, there are 12 ways. With three suits of the same multiplicity, as in 4333, there are 4 ways (this is why this distribution ranks so low). Since 13 is odd, there cannot be four suits with the same multiplicity or two pairs with equal multiplicity. distrib. # hands rank distrib. # hands rank 4333 4 (13 4 )(13 3 )3 5 (10.5%) 7420 24 (13 7 )(13 4 )(13 2 )(13 0 ) 19 (0.36%) 4432 12 (13 4 )2(13 3 )(13 2 ) 1 (21.6%) 7510 24 (13 7 )(13 5 )(13 1 )(13 0 ) 23tie (0.11%) 4441 4 (13 4 )3(13 1 ) 10 (3.0%) 7600 12 (13 7 )(13 6 )(13 0 )2 30 (.0056%) 5332 12 (13 5 )(13 3 )2(13 2 ) 2 (15.5%) 8221 12 (13 8 )(13 2 )2(13 1 ) 21 (0.19%) 5422 12 (13 5 )(13 4 )(13 2 )2 4 (10.6%) 8311 12 (13 8 )(13 3 )(13 1 )2 22 (0.12%) 5431 24 (13 5 )(13 4 )(13 3 )(13 2 ) 3 (12.9%) 8320 24 (13 8 )(13 3 )(13 2 )(13 0 ) 23tie (0.12%) 5440 12 (13 5 )(13 4 )2(13 0 ) 13 (1.2%) 8410 24 (13 8 )(13 4 )(13 1 )(13 0 ) 26 (0.045%) 5521 12 (13 5 )2(13 2 )(13 1 ) 9 (3.2%) 8500 12 (13 8 )(13 5 )(13 0 )2 31 (0.0031%) 5530 12 (13 5 )2(13 3 )(13 0 ) 14 (0.9%) 6322 12 (13 6 )(13 3 )(13 2 )2 6 (5.6%) 9211 12 (13 9 )(13 2 )(13 1 )2 27 (0.018%) 6331 12 (13 6 )(13 3 )2(13 1 ) 8 (3.4%) 9220 12 (13 9 )(13 2 )2(13 0 ) 29 (.0082%) 6421 24 (13 6 )(13 4 )(13 2 )(13 1 ) 7 (4.7%) 9310 24 (13 9 )(13 3 )(13 1 )(13 0 ) 28 (0.010%) 6430 24 (13 6 )(13 4 )(13 3 )(13 0 ) 12 (1.3%) 9400 12 (13 9 )(13 4 )(13 0 )2 33 (.00097%) 6511 12 (13 6 )(13 5 )(13 1 )2 15 (0.71%) 10,1,1,1 4 (13 10 )(13 1 )3 34 (.00040%) 6520 24 (13 6 )(13 5 )(13 2 )(13 0 ) 16 (0.65%) 10,2,1,0 24 (13 10 )(13 2 )(13 1 )(13 0 ) 32 (.0011%) 6610 12 (13 6 )2(13 1 )(13 0 ) 25 (0.072%) 10,3,0,0 12 (13 10 )(13 3 )(13 0 )2 35 (.00016%) 7222 4 (13 7 )(13 2 )3 17 (0.51%) 11,1,1,0 12 (13 11 )(13 1 )2(13 0 ) 36 (.000025%) 7321 24 (13 7 )(13 3 )(13 2 )(13 1 ) 11 (1.9%) 11,2,0,0 12 (13 11 )(13 2 )(13 0 )2 37 (.000011%) 7330 12 (13 7 )(13 3 )2(13 0 ) 20 (0.26%) 12,1,0,0 12 (13 12 )(13 1 )(13 0 )2 38 (.0000003%) 7411 12 (13 7 )(13 4 )(13 1 )2 18 (0.39%) 13,0,0,0 4 39 (6 × 10−10%) 5.25. Inductive proof of (n k ) = n!k!(n−k)! . The formula holds for n = 0 under the convention that the “factorial” of a negative number is infinite. For n > 1, we apply Pascal’s Formula and the induction hypothesis to obtain(n k ) = (n−1k )+ (n−1k−1) = (n−1)!k!(n−1−k)! + (n−1)!(k−1)!(n−k)! = n−kn n!k!(n−k)! + kn n!k!(n−k)! = n!k!(n−k)! . 5.26. The binomial theorem by induction on n. For the basis step, we have (x + y)0 = 1 = (00)x0 y0. Now suppose that the expansion formula holds when the exponent is n. We consider the summation when the parameter is n + 1. The induction hypothesis tells us that (x + y)n = ∑nk=0 (nk)xk yn−k . Since we want the expansion for (x+y)n+1, we multiply both sides by (x+y). To simplify the resulting expression, we want want to combine the terms where the exponents on x agree and on y agree. Therefore, we shift the index in the first summation. We then use Pascal’s Formula to combine corresponding terms in the two summations. For the terms that don’t pair up, we have (n n ) = 1 = (n+1n+1) and (n0) = 1 = (n+10 ), so these become the top and bottom terms of the desired summation. The full computation is (x + y)n+1 = (x + y) n∑ k=0 ( n k ) xk yn−k = n∑ k=0 (