HW 7 Answer Key

Section 4.1

10 We have two choices for each bit, so there are 2^{8} = 256 bit strings.

14 If n = 0, then the empty string vacuously satisfies the condition. if n = 1, then there is one, namely the string 1. If n ≥ 2, then such a string is determined by specifying the n − 2 bits between the first bit and the last, so there are 2^{n−2} such strings.

18. It will be useful to note first that there are exactly 9000 numbers in this range.

a. 1000 Every ninth number is divisible by 9, so the answer is one ninth of 9000. b. 4500 Every other number is even so half of 9000 c. 9 · 9 · 8 · 7 = 4356 REMEMBER: the first number can’t be 0 so there are 9 choices 1 − 9 The second number can’t be equal to the first number but CAN be 0 The third and the fourth numbers in turn can’t be equal d. 6000 Every third number is divisible by 3, so one third of 9000 or 3000 numbers in this range are divisible by 3. The remaining are not. e. 1800 + 1286 − 257 = 2829 one fifth of the numbers in this range, or 1800 of these are divisible by 5 One seventh of them or 1286 are divisible by 7. We need to know the numbers divisible by 5 and 7, which means divisible by 35. There are 257 numbers divisible by 35. f.6171 = 9000 − 2829 Since we just found that 2829 of these numbers are divisible by either 5 or 7, it follows that the rest of them 9000 − 2829 = 6171 are not. g. 1543 = 1800 − 257. 1800 numbers are divisible by 5, of these 257 are also divisible by 7 h)257 - We found this as part of our solution to part e

22. 10^{3} · 26^{3} + 26^{3} · 10^{3} = 35, 152, 000.

33 2^{n/2} if n is even, 2^{(n+1)/2} if n is odd.

The basic idea is that if n is even, we have a choice of 0 or 1 for n/2 bits(first or last), and if n is odd, we have a choice of 0 or 1 for (n−1)/2 bits, and also for the middle bit.So the answer is 2^{(n−1)/2}+2 = 2^{(n+1)/2}.

34 a. (9 · 8 · 7 · 6 · 5) · 6 = 90720 Place the bride in any of the 6 positions. Then, from left to right in the remaining positions, we choose the other five people to be in the picture; this can be done in 9 · 8 · 7 · 6 · 5 = 15120 ways. Therefore the answer is 6 · 15120 = 90720 b. (6 · 5) · (8 · 7 · 6 · 5) = 30 · 1680 = 50400 Place bride in any of the 6 positions, then place the groom in any of the 5 remaining positions. Then from left to right fill in remaining position, we choose the other four people. c. 80640 ¿From part a there are 90720 ways for the bride to be in the picture. ¿From part b, there are 50400 ways for both the bride and groom to be in the picture. Therefore there are 90720 − 50400 = 40320 ways for just the bride to be in the picture. Symetrically there are 40320 ways for just the groom to be in the picture.Therefore the answer is 2 ∗ 40320 = 80640.

42.The first character of the variable name can be selected in 53 ways.(2 ∗ 26 for letters and an underscore to choose from).The remaining i − 1 characters can be chosen in 53 + 10 = 63 ways. Therefore the answer

is ∑_{i=1}^{8} 53.63^{(}i − 1) = 53 · \frac{63^{8}−1}{63−1} which is approximately 2.1 ∗ 10^{14}.

Section 4.2

2 This follows from the pigeonhole principle, with k = 26.

4 There are only d possible remainders when an integer is divided by d, namely 0,1,2...,d-1.By the pigeonhole principle, if we have d + 1 remainders, then at least two must be the same.

5. Let a, a + 1, · · a + n − 1 be the integers in the sequence. The integers (a + i) mod n, i = 0, 1, 2 · ·n − 1, are distinct, since 0 < (a + j) − (a + k) < n whenever 0 ≤ k < j ≤ n − 1. Since there are n possible values for c(a + i)modn, and there are n different integers, each of these values is taken on exactly once. Hence there is exactly one integer divisible by n.

8.The midpoint of the segment whose end-points are (a, b) and (c, d) is ((a+c)/2),(b+d)/2). The coordinates of these fractions will be integers if and only if a and c have the same parity(both odd or both even) and b and d have the same parity. There are 4 possible pair of parities:(odd,odd), (odd,even), (even,odd), (even,even). Since there are 5 points the pigeonhole principle guarantees that at least two of them would have the same pair of parities. The midpoint of the segment joining these two points will therefore have integer coordinates.

12a. We can group the first ten positive integers into five subsets of two integers each, each subset adding up to 11: (1,10), (2, 9), (3,8), (4,7), (5,6). If we select seven integers from this set, then by the pigeonhole principle at least two of them comre from the same subset. Furthermore, if we forget about these two in the same group, then there are five more integers and four groups; again the pigeonhole principle guarantees two integers in the same group. This gives us two pairs of integers, each pair from the same group. In each case these two integers have a sum of 11, as desired. b. No. The set (1,2,3,4,5,6) has only 5 and 6 from the same group, so the only pair with the sum 11 is 5 and 6.

26 Let K(x) be the number of other computers that computer x is connected to. The possible values for K(x) are 1, ..., 5. Since thee are 6 computers the pigeonhole principle guarantees that at least two of the values K(x) are the same.

34 Suppose this statement were not true. Then for i, the i^{th} box contains at most n_{i} − 1 objects. Adding we have at most (n_{1} − 1) + (n_{2} − 1) + ⋯ + (n_{t} − 1) = n_{1} + n_{2}, + ⋯ +n_{t} − t objects in all. This contradicts the fact that there were n_{1} + n_{2}, + ⋯ +n_{t} − t + 1 objects in all. Therefore the statement must be true.

Section 4.3

6.a. C(5, 1) = 5 b. C(5, 3) = C(5, 2) = 5 · 4/2 = 10 c. C(8, 4) = 70 d. C(8, 8) = 1 e. C(8, 0) = 1 f. C(12, 6) = 924

8.P (5, 5) = 5! = 120.

14. 512 There are 2^{10} = 1024 subsets in all, 1/2 of them contain an even number 1/2 contain and odd. Or C(10, 1) + C(10, 3) + C(10, 5) + C(10, 7) + C(10, 9) = 10 + 120 + 242 + 120 + 10 = 512

20. C(40, 17) or about 8.9 ∗ 10^{10} We are asked for the number of strings of T’s and F’s of length 40 with exactly 17 T’s.

24 a. The only reasonable way to do this is by subtracting from the number of strings with no restrictions the number of strings that do not contain the letter a. The answer is 26^{5} − 25^{5} = 2, 115, 751. b. 26^{5} − (25^{5} + 25^{5} − 24^{5}) = 312, 750 If the string is to contain both letters, then we need to subtract from the total number of strings the number that don’t contain a or b, or both. 25^{5} strings don’t contain a, 25^{5} don’t contain b. However 24^{5} strings don’t contain a or b. These were counted twice. Therefore the answer is 26^{5} − (25^{5} + 25^{5} − 24^{5}). c. 5 ∗ P (24, 4) = 1, 275, 120 First choose the position for ac. This can be done in 5 ways since b must follow it. There are four remaining positions, and these can be filled in P (24, 4) ways, since there are 24 letters left (no repetitions allowed.) d. C(6, 2) · P (24, 4) = 3, 825, 360. First choose the positions for a and b; This can be done in C(6,2) ways. There are four remaining positions to be filled in P(24,4) ways. (no repetitions).

28. Glue two 1’s to the right of each 0, giving us a collection of 9 tokens: five 011’s and four 1’s. We are asked for the no. of strings consisting of these tokens. All that is involved is choosing positions for the 1’s among the 9 positions, so the answer is C(9, 4) = 126.

32.We might as well assume that the first person sits in the northernmost seat. Then there are P(5,5) ways to seat the remaining people, since they form a permutation reading clockwise from the first person. Therefore the answer is 5! = 120.

40.C(17, 9) · 3^{8} · 2^{9} = 24310 · 6561 · 512 = 81, 662, 929, 920.

42 By the binomial theorem, the typical term in this expansion is C(100, j)x^{100−j}(1/x)^{j}, which simplifies to C(100, j)x^{100−2j}. As j runs from 0 to 100, the exponent runs from 100 down to -100 in decrements of 2. If we let k denote the exponent, then solving k = 100 − 2j for j we obtain j = (100 − k)/2. Thus the values of k for which x^{k} appears in this expansion are -100, -98, ..., -2, 0, 2, 4, ..., 100, and for such values of k the coefficient is C(100, (100 − k)/2)

. 50a. To choose 2 people from a set of n men and n women, we can either choose 2 men or 2 women (C(n, 2) ways to to either) or one of each sex (n · n ways to do so.) Therefore the right-hand side counts the number of ways to do this (by the sum rule). The left-hand side counts the same thing, since we are simply choosing 2 people from 2n people. b. 2C(n, 2) + n^{2} = n(n − 1) + n^{2} = 2n^{2} − n = n(2n − 1) = 2n(2n − 1)/2 = C(2n, 2)