\documentclass[11pt]{exam} \usepackage{graphicx} \usepackage{anysize} \usepackage{dsfont} \usepackage{fullpage} \usepackage{verbatim} \usepackage{url,amsfonts, amsmath, amssymb, amsthm,color, enumerate, multicol} \usepackage{placeins} \printanswers %\noprintanswers \begin{document} \title{ EECS 203: Discrete Mathematics \\ Individual Homework 6 (Winter 2016)} \date{Due: June 9, 2016} \author{Answer Key} \maketitle \begin{questions} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \question[2] Section 4.4 Problem 22\\ %% \begin{solution} By definition, the first congruence can be written as x = 6t + 3 where t is an integer. Substituting this expression for x into the second congruence tells us that $6t + 3 \equiv 4 \mod 7$, which can easily be solved to show that $t \equiv 6 \mod 7$. From this we can write t = 7u + 6 for some integer u. Thus x = 6t + 3 = 6(7u + 6) + 3 = 42u + 39. Thus our answer is all numbers congruent to 39 modulo 42. We check our answer by confirming that $39 \equiv 3 \mod 6$ and $39 \equiv 4 \mod 7$. \end{solution} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \question[2] Section 5.1 Problem 50\\ %% \begin{solution} When n = 1 the left-hand side is 1, and the right-hand side is $(1+\frac12)^2/2=9/8$. Thus the basis step was wrong. \end{solution} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \question[3] Section 5.2 Problem 8\\ %% \begin{solution} Since both 25 and 40 are multiples of 5, we cannot form any amount that is not a multiple of 5. So let’s determine for which values of n we can form 5n dollars using these gift certificates, the first of which provides 5 copies of \$5, and the second of which provides 8 copies. We can achieve the following values of n:\\ 5 = 5,\\ 8 = 8,\\ 10 = 5+5,\\ 13 = 8+5,\\ 15 = 5+5+5,\\ 16 = 8+8,\\ 18 = 8+5+5,\\ 20 = 5+5+5+5+5,\\ 21 = 8+8+5,\\ 23 = 8 + 5 + 5 + 5,\\ 24 = 8 + 8 + 8,\\ 25 = 5 + 5 + 5 + 5 + 5,\\ 26 = 8 + 8 + 5 + 5,\\ 28 = 8 + 5 + 5 + 5 + 5,\\ 29 = 8 + 8 + 8 + 5,\\ 30 = 5 + 5 + 5 + 5 + 5 + 5,\\ 31 = 8 + 8 + 5 + 5 + 5,\\ 32 = 8 + 8 + 8 + 8. By having considered all the combinations, we know that the gaps in this list cannot be filled. We claim that we can form total amounts of the form 5n for all $n \geq 28$ using these gift certificates. (In other words, \$135 is the largest multiple of \$5 that we cannot achieve.) To prove this by strong induction, let P(n) be the statement that we can form 5n dollars in gift certificates using just 25-dollar and 40-dollar certificates. We want to prove that P(n) is true for all $n \geq 28$. From our work above, we know that P(n) is true for n = 28, 29, 30, 31, 32. Assume the inductive hypothesis, that P(j) is true for all j with $28 \leq j \leq k$ , where k is a fixed integer greater than or equal to 32. We want to show that P(k + 1) is true. Because $k - 4 \geq 28$, we know that P(k - 4) is true, that is, that we can form 5(k - 4) dollars. Add one more \$25-dollar certificate, and we have formed 5(k + 1) dollars, as desired. \end{solution} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \question[1] Section 5.2 Problem 32\\ %% \begin{solution} The proof is invalid for k = 4. We cannot increase the postage from 4 cents to 5 cents by either of the replacements indicated, because there is no 3-cent stamp present and there is only one 4-cent stamp present. There is also a minor flaw in the inductive step, because the condition that $j \geq 3$ is not mentioned. \end{solution} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \question[2] Section 6.1 Problem 22 (d, h)\\ %% \begin{solution} \begin{enumerate}[a)] \addtocounter{enumi}{3} \item Every seventh number is divisible by 7. Therefore there are $\lfloor999/7\rfloor = 142$ such numbers. Note that we use the floor function, because the $k^{th}$ multiple of 7 does not occur until the number 7k has been reached. There are $\lfloor999/11\rfloor = 90$ numbers in our range divisible by 11, and there are $\lfloor999/77\rfloor = 12$ numbers in our range divisible by both 7 and 11 (the multiples of 77 are the numbers we seek). By the principle of inclusion-exclusion, the answer is 142 + 90 - 12 = 220. \addtocounter{enumi}{3} \item First, we count the even 1-digit numbers with all distinct digits. There is only 1 digit, so all 4 of them have distinct digits.\\ Next, we count the 2-digit numbers. This time we break it into 2 cases: numbers ending in a 0 and numbers not ending in a 0. If it ends in a 0, all non-0 digits in the tens place will work, giving 9 numbers. If it does not, the tens place must differ and be non-0, giving 8 options for 4*8=32 total possibilities.\\ For 3-digit numbers, we will break them up in the same way. If it ends in a 0, the hundreds place can be any non-0 digit and the tens place can be any digit other than the 2 already chosen, giving 9*8=72 options. If it does not end in a 0, the hundreds place can be any of the other 8 non-0 digits, while the tens place can be any of the other 7 non-0 digits or 0, giving 4*8*8=256 numbers.\\ In total we have $4+9+32+72+256=373$ numbers satisfying the requirements. \end{enumerate} \end{solution} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \question[1] Section 6.1 Problem 34 (c)\\ %% \begin{solution} In each case the answer is $n^{10}$ , where n is the number of elements in the codomain, since there are n choices for a function value for each of the 10 elements in the domain. c) $4^{10} = 1,048,576$ \end{solution} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \question[2] Section 6.2 Problem 16\\ %% \begin{solution} We can apply the pigeonhole principle by grouping the numbers cleverly into pairs (subsets) that add up to 16, namely \{1, 15\}, \{3, 13\}, \{5, 11\}, and \{7, 9\}. If we select five numbers from the set \{1, 3, 5, 7, 9, 11, 13, 15\}, then at least two of them must fall within the same subset, since there are only four subsets. Two numbers in the same subset are the desired pair that add up to 16. We also need to point out that choosing four numbers is not enough, since we could choose \{1, 3, 5, 7\}, and no pair of them add up to more than 12. \end{solution} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \question[3] Section 6.2 Problem 28\\ %% \begin{solution} Let A be one of the people. She must have either 10 friends or 10 enemies, since if there were 9 or fewer of each, then that would account for at most 18 of the 19 other people. Without loss of generality assume that A has 10 friends. By Exercise 27 there are either 4 mutual enemies among these 10 people, or 3 mutual friends. In the former case we have our desired set of 4 mutual enemies; in the latter case, these 3 people together with A form the desired set of 4 mutual friends. \end{solution} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \question[3] Section 6.3 Problem 22 (a,d,f)\\ %% \begin{solution} \begin{enumerate}[a)] \item If ED is to be a substring, then we can think of that block of letters as one superletter, and the problem is to count permutations of seven items—the letters A, B, C , F , G, and H , and the superletter ED. Therefore the answer is P(7, 7) = 7! = 5040. \addtocounter{enumi}{2} \item This is similar to part (c). Glue AB into one item, glue DE into one item, and glue GH into one item, producing five items, so the answer is P(5, 5) = 5! = 120. \addtocounter{enumi}{1} \item There are no permutations with both of these substrings, since B cannot be followed by both C and F at the same time. \end{enumerate} \end{solution} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \question[2] Section 6.3 Problem 34\\ %% \begin{solution} Probably the best way to do this is just to break it down into the three cases by sex. There are C(15, 6) ways to choose the committee to be composed only of women, C(15, 5)C(10, 1) ways if there are to be five women and one man, and C(15, 4)C(10, 2) ways if there are to be four women and two men. Therefore the answer is C(15, 6) + C(15, 5)C(10, 1) + C(15, 4)C(10, 2) = 5005 + 30030 + 61425 = 96,460. \end{solution} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \question[3] Chapter 6 Supplementary Exercises Problem 28\\ %% \begin{solution} The base case is n = 2, in which case the identity simply states that 1 = 1. Assume the inductive hypothesis, that $\sum_{j=2}^n C(j, 2) = C(n + 1, 3)$. Then $$\sum_{j=2}^{n+1}C(j, 2) =\left(\sum_{j=2}^nC(j,2)\right)+C(n+1,2)= C(n + 1, 3) + C(n + 1, 2) = C((n + 1) + 1, 3)$$ as desired. The last equality made use of Pascal’s identity. \end{solution} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \question[2] Section 6.5 Problem 6\\ %% \begin{solution} In this case, we have 5 stars with 2 bars, so the answer is C(5 + 2, 5) = C(7, 5) = C(7, 2) = 21. \end{solution} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \question[4] Section 6.5 Problem 16 (b,d)\\ %% \begin{solution} \begin{enumerate}[a)] \addtocounter{enumi}{1} \item The restrictions use up 22 of the total, leaving a free total of 7. Therefore the answer is 7 stars, 5 bars, giving C(7 +5, 7) = C(12, 7) = 792. \addtocounter{enumi}{1} \item The number of solutions with $x_2 \geq 9$ (as required) but without the restriction on $x_1$ is 20 stars 5 bars, giving C(20 +5, 20) = C(25, 20) = 53130. The number of solution violating the additional restriction by having $x_1 \geq 8$ is 12 stars 5 bars, giving C(12 +5, 12) = C(17, 12) = 6188. Therefore the answer is 53130 - 6188 = 46,942. \end{enumerate} \end{solution} \end{questions} \end{document}