MATH 55 SOLUTION SET—SOLUTION SET #5

Note. Any typos or errors in this solution set should be reported to the GSI at isammis@math.berkeley.edu 4.1.8. How many different three-letter initials with none of the letters repeated can people have. Solution. One has 26 choices for the first initial, 25 for the second, and 24 for the third, for a total of (26)(25)(24) possible initials. 4.1.18. How many positive integers less than 1000 (a) are divisible by 7? (b) are divisible by 7 but not by 11? (c) are divisible by both 7 and 11? (d) are divisible by either 7 or 11? (e) are divisible by exactly one of 7 or 11? (f ) are divisible by neither 7 nor 11? (g) have distinct digits? (h) have distinct digits and are even? Solution. (a) Every 7th number is divisible by 7. Since 1000 = (7)(142) + 6, there are 142 multiples of seven less than 1000. (b) Every 77th number is divisible by 77. Since 1000 = (77)(12) + 76, there are 12 multiples of 77 less than 1000. We don’t want to count these, so there are 142 − 12 = 130 multiples of 7 but not 11 less than 1000. (c) We just figured this out to get (b)—there are 12. (d) Since 1000 = (11)(90) + 10, there are 90 multiples of 11 less than 1000. Now, if we add the 142 multiples of 7 to this, we get 232, but in doing this we’ve counted each multiple of 77 twice. We can correct for this by subtracting off the 12 items that we’ve counted twice. Thus, there are 232-12=220 positive integers less than 1000 divisible by 7 or 11. (e) If we want to exclude the multiples of 77 altogether, we need only subtract them off a second time; there are thus 220-12=208 multiples of 7 or 11 but not both. (f) There are 999 positive integers less than 1000. We’ve accounted for 220 as multiples of 7 or 11, so there are 779 that are divisible by neither. (g) There are 9 one-digit positive numbers. For two-digit numbers, the first digit may be anything from 1 to 9, while the second may be anything from 0 to 9 except the first digit. We thus have 9 choices for each digit, and so have 81 two-digit numbers with distinct digits. For three-digit numbers, we have 9 choices for the first digit, 9 for the second, and 8 for the third, for a total of 648 three-digit numbers with distinct digits. Thus, there are 9+81+648=738 numbers less than 1000 with distinct digits.
Typeset by AMS-TEX

1

2

MATH 55 SOLUTION SET—SOLUTION SET #5

(h) This time things get a little tricky. There are 4 one-digit even numbers. For two digit numbers, there are 4 nonzero choices for the second digit, upon which we have 8 choices of first digit, or the last digit could be zero, upon with we have 9. There are thus 41 even two-digit numbers with distinct digits. For three-digit numbers, there are 4 nonzero last digits, upon which there are 8 choices of first digit and 8 of middle digit (for (4)(8)(8)=256 choices, or the last digit is zero, upon which there are 9*8=72 such numbers. There are thus 4+41+256+72=373 even numbers less than 1000 with distinct digits. 4.1.22. How many strings of four decimal digits (a) do not contain the same digit twice? (b) end with an even digit? (c) have exactly three digits that are 9s? Solution. (a) If you can’t reuse digits, we have 10 choices of a first digit, 9 of a second, 8 of a third, and 7 of a fourth, for (10)(9)(8)(7)=5040 such strings. (b) We have 10 choices each for the first three digits, then 5 for the final digit, for (103 )(5) = 5000 strings. (c) We have 4 choices of where to put the digit that isn’t a 9. It may be any digit except a 9, so we have 9 choices of a non-9 digit. There are thus 36 such strings. 4.1.40. How many bit strings of length seven either begin with two 0s or end with three 1s? Solution. The number of bit strings of length 7 that begin with two 0s is just the number of five-bit strings: 25 . The number of bit strings that end in three 1s is 24 . Since the two cases aren’t mutually exclusive, we have to use inclusion/exclusion to avoid counting the 4 overlap strings twice. Thus, the number of such bit strings is 25 + 24 − 4 = 32 + 16 − 4 = 44. 4.1.44. Every student in a discrete mathematics class is either a computer science or a mathematics major or is a joint major in these two subjects. How many students are in the class if there are 38 computer science majors (including joint majors), 23 mathematics majors (including joint majors), and 7 joint majors. Solution. This is a classic inclusion/exclusion problem—there are 38 + 23 − 7 = 54 students in the class. If you’re still having trouble understanding what’s going on in problems like this, the key is to keep track of how many times any single student has been counted. After counting the CS majors, each CS major has been counted once. After counting the math majors, the single-majors have each been counted once, but the double majors have been counted twice—once as CS majors, then again as math majors. If we subtract their number off, we’ll have counted each student exactly once. 4.1.48. Use a tree diagram to find the number of bit strings of length four with no three consecutive 0s.

MATH 55 SOLUTION SET—SOLUTION SET #5

3

Solution. First digit Second Digit Third digit 0 00 000x 001 01 010 011 1 10 100 101 11 110 111 So there are 13 such strings. 4.1.58. Data are transmitted over the Internet in datagrams, which are structured blocks of bits. Each datagram contains header information organized into a maximum of 14 different fields (specifying many things, including the source and destination addresses) and a data area that contains the actual data that are transmitted. One of the 14 header fields is the header length field (denoted by HLEN), which is specified by the protocol to be 4 bits long and that specifies the header length in terms of terms of 32-bit blocks of bits. For example, if HLEN=0110, the header is made up of six 32-bit blocks. Another of the 14 header fields is the 16-bit-long total length field (denoted by TOTAL LENGTH), which specifies the length in bits of the entire datagram, including both the header fields and the data area. The length of the data area is the total length of the datagram minus the length of the header. (a) The largest possible value of TOTAL LENGTH (which is 16 bits long) determines the maximum total length in octets (blocks of 8 bits) of an internet datagram. What is this value? (b) The largest possible value of HLEN (which is 4 bits long) determines the maximum total header length in 32-bit blocks. What is this value? What is the maximum total header length in octets? (c) The minimum (and most common) header length is 20 octets. What is the maximum total length in octets of the data area of an Internet datagram? (d) How many different strings of octets in the data area can transmitted if the header length is 20 octets and the total length is as long as possible? Solution. (a) The largest possible value of any N -bit number is 2N − 1, so the largest possible TOTAL LENGTH is 216 − 1 = 65535. The book is a bit confusing here—it claims that this field is in bytes (octets) here, while earlier it claimed it was in bits. Fortunately, IP datagrams are real things that can be looked up easily; the total length field is in fact in bytes. Thus, the biggest possible datagram is 65535 bytes, one byte short of 64K. Fourth digit 0010 0011 0100 0101 0110 0111 1000x 1001 1010 1011 1100 1101 1110 1111

4

MATH 55 SOLUTION SET—SOLUTION SET #5

(b) HLEN ca be at most 24 − 1 = 15. This is the maximum number of 32-bit blocks, so the header can be at most 32 × 15 = 480 bytes long (c) Since the biggest datagrams are 65535 bytes, if the smallest header is 20 bytes then the largest data area is 65515 bytes. (d) Since you can freely choose any byte to take on any of 256 values, there are 25665516 possible datagrams of maximum data length. 4.2.6. Let d be a positive integer. Show that among any group of d + 1 (not necessarily consecutive) integers there are two with exactly the same remainder when divided by d. Solution. From chapter 2, we remember that remainders after division by d must fall in the range 0 ≤ r ≤ d − 1; that is, there are precisely d different remainders. By the pigeonhole principle, at least two of any collection of d + 1 integers must have the same remainder when divided by d. 4.2.10. Let (xi , yi ), i = 1, 2, 3, 4, 5 be a set of points with integer coordinates in the xy plane. Show that the midpoint of the line joining at least one pair of these points has integer coordinates. Solution. The midpoint of the line connecting (xi , yi ) and (xj , yj ) is i 2 j , i 2 j . For such a point to be at integer coordinates, we must have xi ≡ xj (mod 2) and yi ≡ yj (mod 2). There are four possible combinations (xi , yi ) (mod 2) down to congruency: (0, 0) (mod 2), (0, 1) (mod 2), (1, 0) (mod 2), and (1, 1) (mod 2). With five points, at least two of them must be identical to congruency (mod 2), and so must be joined by a segment with midpoint at integer coordinates. 4.2.12. How many ordered pairs of integers (a, b) are needed to guarantee that there are at least two ordered pairs (a1 , b1 ) and (a2 , b2 ) such that a1 mod 5 = a2 mod 5 and b1 mod 5 = b2 mod 5? Solution. This is nearly identical to the previous problem. The only difference is that this time there are 52 possible ordered pairs of remainders mod 5, so we must have at least 26 ordered pairs to guarantee a matching set of pairs. 4.2.20. Find an increasing subsequence of maximal length and a decreasing subsequence of maximal length in the sequence 22,5,7,2,23,10,15,21,3,17. Solution. Since 10 = 32 + 1, we are guaranteed a subsequence of length 4 that’s either increasing or decreasing. It’s fairly easy to find at least one increasing subsequence of length 5: 5, 7, 10, 15, 21. It’s also easy to verify (by checking all 10 = 210 such sequences, if necessary) that no increasing subsequence of length 6 6 exists. As for decreasing sequences, since we’ve found an increasing sequence of length greater than 4, there doesn’t necessarily exist a decreasing subsequence of this length. Indeed, a lot of tedious checking confirms that the longest decreasing sequences are of length 3 (22,15,3, for example). 4.2.24. Show that in a group of five people (where any two people are either friends or enemies), there are not necessarily three mutual friends or three mutual enemies. x +x y +y

MATH 55 SOLUTION SET—SOLUTION SET #5

5

Solution. Consider the following structure: Person Friends A C, D B D, E C A, E D A, B E B, C Enemies B, E A, C B, D C, E A, D

It may be verified easily that no three people are mutual friends. 4.3.14. In how many ways can a set of two positive integers less than 100 be chosen? Solution. Since we don’t care about the order in which the two integers are chosen, this is just C(99, 2) = (99)(98)/2 = 4, 851 ways. To see this, note that we have 99 choices for the first number, then 98 for the second. Because we don’t care about ordering, we’ve precisely double-counted each possible set of two integers, so we should divide by two to get the number of possible sets. 4.3.28. A professor writes 40 discrete mathematics true/false questions. Of the statements in those questions, 17 are true. If the questions can be positioned in any order, how many different answer keys are possible? Solution. An answer key is just a list that maps the numbers 1, . . . , 40 to the set {T, F }. Since we know that precisely 17 numbers map to T , we’re done as soon as we choose 17 numbers from the set 1, 2, . . . , 40. This is precisely the question 40! combinations are designed to solve–the answer is just C(40, 17) = 17!23! . If you’re bored or curious, you can work out that this is 88, 732, 378, 800. 4.3.32. How many strings of six lowercase letters from the English alphabet contain (a) the letter a? (b) the letters a and b? (c) the letters a and b in consecutive positions with a preceding b, with all letters distinct? (d) the letters a and b, where a is somewhere to the left of b in the string with all letters distinct? Solution. (a) There are 266 possible 6-character strings. There are 256 that contain no a at all. Thus, there are 266 − 256 strings containing the letter a. (b) This one’s a bit of a shell game, so keep your eyes open. There are 256 6character strings that don’t use the letter b. There are also 256 6-character strings that don’t use the letter a. There are 246 6-character strings that don’t use either a or b. So—there are 266 − 246 strings that have an a, a b, or both. There are 256 − 246 that use an a but not a b. Similarly, there are 256 − 246 strings that use a b but not an a. So, the number of strings that contain an a and a b is just 266 − 246 − 2(256 − 246 ) = 266 − (2)256 + 246 . (c) There are 5 possible places where one could place the ab. This leaves four additional characters, which we can choose in order, in (24)(23)(22)(21) ways. There are thus (5)(24)(23)(22)(21) such strings. (d) Now, we must choose two positions that will contain the a and the b. We don’t care about ordering—we’ve been given that the a will be to the left of the

6

MATH 55 SOLUTION SET—SOLUTION SET #5

b. There are C(6, 2) = 15 ways to choose these two positions. From this point, the problem looks just like the previous one, so there are (15)(24)(23)(22)(21) such strings. 4.4.8. What is the coefficient of x8 y 9 in the expansion of (3x + 2y)1 7? Solution. First of all, if x is taken to the 8th power, then so must 3, and if y is taken to the 9th power, so must 2. Now, the number of ways to arrive at such a 17 17 term is . Thus, the coefficient of x8 y 9 is 38 29 . 8 8 4.4.12. The row of Pascal’s triangle containing the binomial coefficients 0 ≤ k ≤ 10, is: 1 10 45 120 210 252 210 120 45 10 1 Use Pascal’s identity to produce the row immediately following this row in Pascal’s triangle. Solution. By Pascals identity, the first half of next row is 1 1 + 10 10 + 45 45 + 120 120 + 210 1 11 55 165 330 462 462 330 210 + 252 55 11 n 2 ··· 1 + n2 with the rest determined by symmetry. Thus, the next row is 165 2n 2 10 , k

4.4.28. Show that if n is a positive integer, then (a) using a combinatorial argument. (b) by algebraic manipulation Solution.

=2

2n represents the number of way to choose 2 items from 2 a group of 2n. Imagine taking the 2n items and arranging them into two piles of n items each. If we are to choose two items, there are three possibilities: two items n n from pile 1 (for which there are possibilities), two from pile 2 (another 2 2 2n n possibilities), or one from each pile (n2 possibilities). Thus, =2 + n2 , 2 2 as claimed. (b) By algebraic manipulation: (a) Combinatorially, 2 n 2 + n2 = 2(n!) + n2 2!(n − 2)! 2(n)(n − 1) = + n2 2 = n2 − n + n2 = 2n2 − n 2n 2 = (2n)(2n − 1) 2

= 2n2 − n

MATH 55 SOLUTION SET—SOLUTION SET #5

7

4.5.10—The Dreaded Croissant Problem. A croissant shop has plain croissants, cherry croissants, chocolate croissants, almond croissants, apples croissants, and broccoli croissants. How many ways are there to choose (a) a dozen croissants? (b) three dozen croissants? (c) two dozen croissants with at least two of each kind? (d) two dozen croissants with no more than two broccoli croissants? (e) two dozen croissants with at least five chocolate croissants and at least three almond croissants? (f ) two dozen croissants with at least one plain croissant, at least two cherry croissants, at least three chocolate croissants, at least one almond croissant, at least two apple croissants, and no more than three broccoli croissants? Solution. (a) As usual in problems of this ilk, we can think of the problem as one of where to put the dividing lines between the 6 types of croissant. Since we have 12 17 croissants and 5 dividing lines, there are ways to choose croissants. 5 (b) This is just like the last problem, but with more croissants. This time we 41 have 36 croissants and 5 dividing lines, for ways to choose croissants. 5 (c) We can start the problem by choosing the croissants that we’re obliged to have: 12 croissants (two of each type). Once we’ve done that, we’re free to choose the remaining 12 croissants as we see fit. We’ve already solved that problem in part 17 (a): . 5 (d) There are two basic approaches to this problem. We could work by cases of numbers of broccoli croissants—for any number of broccoli croissants, we can choose the rest freely (with only 4 dividing lines; we’ve already dealt with broccoli). 28 If we’re sensible and choose no broccoli croissants, then there are ways of 4 27 choosing croissants. If we choose one, there are ways of choosing croissants; 4 26 if there are two, then there are ways of choosing. Thus, there are a total of 4 28 4 + 27 4 + 26 4

ways of choosing croissants. The other possible approach is by inclusion/exclusion. If we choose at least 260 three broccoli croissants (first), then there are ways of choossing two dozen 5 29 croissants. Since there are ways of choosing 24 croissants freely, there are 5 29 5 − 26 5

ways of choosing croissants such that there are no more than three butter croissants. Either method results in the same number: 52,975 ways of choosing croissants.

8

MATH 55 SOLUTION SET—SOLUTION SET #5

(e) This one’s easier–we’ve pre-chosen eight croissants, leaving us with 16 choose. 21 There are thus ways of choosing croissants. 5 (f) This is just a combination of the last two sorts of problems. We can do this one by inclusion/exclusion, after we account for the “necessary” eight croissants. If we ignore the ”no more than 3” condition, there are 16 croissants to choose freely, 21 or possible combinations of croissants. If we also grab at least four broccoli 5 17 croissants, then there are possible combinations. Thus, there are 5 21 5 − 17 5

possible combinations of croissants that meet all the conditions. 4.5.14. How many solutions are there to the equation x1 + x2 + x3 + x4 = 17, where x1 , x2 , x3 , x4 are nonnegative integers? Solution. This is precisely a ”17 balls in 4 pots” problem, stripped down to its essentials. As in all such problems, you’re choosing where to put the three dividers 20 that separate the xi , so there are ways of solving this equation. 3 4.5.18. How many strings of 20 decimal digits are there that contain two 0s, four 1s, three 2s, one 3, two 4s, three 5s, two 7s, and three 9s? Solution. If all 20 characters were distinguishable, there would be 20! possible strings. Because so many characters are indistinguishable, we have overcounted badly. Dividing out by all the ways that we can arrange the identical characters, we see that there are: 20! 2!4!3!2!3!2!3! ways of arranging this string. 4.5.44. In how many ways can a dozen books be placed on four distinguishable shelves (a) if the books are indistinguishable copies of the same title? (b) if no two books are the same, and the positions of the books on the shelves matter? Solution. (a) This is a classic “balls into pots” problem—three dividers, 12 items, and so 15 ways of dividing up the books. 3 (b) Now the books are distinct. Imagine making strings from 12 distinct characters and three indistinguishable dividers. There are 15! ways of arranging the characters, with 3! of each string due to overcounting rearrangements of the barriers. Thus, there are 15! 3! ways of arranging the books.

MATH 55 SOLUTION SET—SOLUTION SET #5

9

4.6.12. Find the integers that correspond to these permutations: (a) 246531 (b) 12345 (c) 654321 Solution. In each case, we must count the number of digits less than i + 1 following i + 1 in the string (a) Counting, a1 = 1, a2 = 1, a3 = 2, a4 = 2, a5 = 3, so the integer here is 1(1!) + 1(2!) + 2(3!) + 2(4!) + 3(5!) = 1 + 2 + 12 + 48 + 360 = 423 (b) Since this string is in order, all the ai = 0, and so this is permutation 0. (c) Here ai = i, so 1(1!) + 2(2!) + 3(3!) + 4(4!) + 5(5!) = 719 is the number of this permutation.