Discrete Mathematics Levin 0.2 11 Answers
\(\def\d{\displaystyle} \def\course{Math 228} \newcommand{\f}[1]{\mathfrak #1} \newcommand{\s}[1]{\mathscr #1} \def\N{\mathbb N} \def\B{\mathbf{B}} \def\circleA{(-.5,0) circle (1)} \def\Z{\mathbb Z} \def\circleAlabel{(-1.5,.6) node[above]{$A$}} \def\Q{\mathbb Q} \def\circleB{(.5,0) circle (1)} \def\R{\mathbb R} \def\circleBlabel{(1.5,.6) node[above]{$B$}} \def\C{\mathbb C} \def\circleC{(0,-1) circle (1)} \def\F{\mathbb F} \def\circleClabel{(.5,-2) node[right]{$C$}} \def\A{\mathbb A} \def\twosetbox{(-2,-1.5) rectangle (2,1.5)} \def\X{\mathbb X} \def\threesetbox{(-2,-2.5) rectangle (2,1.5)} \def\E{\mathbb E} \def\O{\mathbb O} \def\U{\mathcal U} \def\pow{\mathcal P} \def\inv{^{-1}} \def\nrml{\triangleleft} \def\st{:} \def\~{\widetilde} \def\rem{\mathcal R} \def\sigalg{$\sigma$-algebra } \def\Gal{\mbox{Gal}} \def\iff{\leftrightarrow} \def\Iff{\Leftrightarrow} \def\land{\wedge} \def\And{\bigwedge} \def\entry{\entry} \def\AAnd{\d\bigwedge\mkern-18mu\bigwedge} \def\Vee{\bigvee} \def\VVee{\d\Vee\mkern-18mu\Vee} \def\imp{\rightarrow} \def\Imp{\Rightarrow} \def\Fi{\Leftarrow} \def\var{\mbox{var}} \def\Th{\mbox{Th}} \def\entry{\entry} \def\sat{\mbox{Sat}} \def\con{\mbox{Con}} \def\iffmodels{\bmodels\models} \def\dbland{\bigwedge \!\!\bigwedge} \def\dom{\mbox{dom}} \def\rng{\mbox{range}} \def\isom{\cong} \DeclareMathOperator{\wgt}{wgt} \newcommand{\vtx}[2]{node[fill,circle,inner sep=0pt, minimum size=4pt,label=#1:#2]{}} \newcommand{\va}[1]{\vtx{above}{#1}} \newcommand{\vb}[1]{\vtx{below}{#1}} \newcommand{\vr}[1]{\vtx{right}{#1}} \newcommand{\vl}[1]{\vtx{left}{#1}} \renewcommand{\v}{\vtx{above}{}} \def\circleA{(-.5,0) circle (1)} \def\circleAlabel{(-1.5,.6) node[above]{$A$}} \def\circleB{(.5,0) circle (1)} \def\circleBlabel{(1.5,.6) node[above]{$B$}} \def\circleC{(0,-1) circle (1)} \def\circleClabel{(.5,-2) node[right]{$C$}} \def\twosetbox{(-2,-1.4) rectangle (2,1.4)} \def\threesetbox{(-2.5,-2.4) rectangle (2.5,1.4)} \def\ansfilename{practice-answers} \def\shadowprops{{fill=black!50,shadow xshift=0.5ex,shadow yshift=0.5ex,path fading={circle with fuzzy edge 10 percent}}} \newcommand{\hexbox}[3]{ \def\x{-cos{30}*\r*#1+cos{30}*#2*\r*2} \def\y{-\r*#1-sin{30}*\r*#1} \draw (\x,\y) +(90:\r) -- +(30:\r) -- +(-30:\r) -- +(-90:\r) -- +(-150:\r) -- +(150:\r) -- cycle; \draw (\x,\y) node{#3}; } \renewcommand{\bar}{\overline} \newcommand{\card}[1]{\left| #1 \right|} \newcommand{\twoline}[2]{\begin{pmatrix}#1 \\ #2 \end{pmatrix}} \newcommand{\lt}{<} \newcommand{\gt}{>} \newcommand{\amp}{&} \)
Solutions for Section 0.2
0.2.1
Solution
0.2.2
Solution Jack passed math or Jill passed math (or both). If Jack and Jill did not both pass math, then Jill did.
0.2.5
Answer The statements are equivalent to the… converse. implication. neither. implication. converse. converse. implication. converse. converse. converse (in fact, this is the converse). implication (the statement is the contrapositive of the implication). neither.
0.2.7
Solution
0.2.8
Solution Any even number plus 2 is an even number. For any \(x\) there is a \(y\) such that \(\sin(x) = y\text{.}\) In other words, every number \(x\) is in the domain of sine. For every \(y\) there is an \(x\) such that \(\sin(x) = y\text{.}\) In other words, every number \(y\) is in the range of sine (which is false). For any numbers, if the cubes of two numbers are equal, then the numbers are equal.
0.2.10
Solution This says that everything has a square root (every element is the square of something). This is true of the positive real numbers, and also of the complex numbers. It is false of the natural numbers though, as for \(x = 2\) there is no natural number \(y\) such that \(y^2 = 2\text{.}\) This asserts that between every pair of numbers there is some number strictly between them. This is true of the rationals (and reals) but false of the integers. If \(x = 1\) and \(y = 2\text{,}\) then there is nothing we can take for \(z\text{.}\) Here we are saying that something is between every pair of numbers. For almost every domain, this is false. In fact, if the domain contains \(\{1,2,3, 4\}\text{,}\) then no matter what we take \(x\) to be, there will be a pair that \(x\) is not between. However, the set \(\{1,2,3\}\) as our domain makes the statement true. Let \(x = 2\text{.}\) Then no matter what \(y\) and \(z\) we pick, if \(y \lt z\text{,}\) then 2 is between them.
Solutions for Section 0.3
0.3.1
Solution Yes. All three elements of \(C\) are also elements of \(A\text{.}\) No. There is an element of \(C\text{,}\) namely the element 2, which is not an element of \(B\text{.}\)
0.3.4
Solution For example, \(A = \{1,2,3\}\) and \(B = \{1,2,3,4,5,\{1,2,3\}\}\)
0.3.5
Solution No. No.
0.3.7
Solution \(A \cup \bar B\text{:}\) \(\bar{(A \cup B)}\text{:}\) \(A \cap (B \cup C)\text{:}\) \((A \cap B) \cup C\text{:}\) \(\bar A \cap B \cap \bar C\text{:}\) \((A \cup B) \setminus C\text{:}\)
0.3.9
Solution 34. 103. 8.
0.3.13
Solution For example, \(A = \{1,2,3,4\}\) and \(B = \{5,6,7,8,9\}\) gives \(A \cup B = \{1,2,3,4,5,6,7,8,9\}\text{.}\)
Solutions for Section 0.4
0.4.1
Solution There are 8 different functions. In two-line notation these are: None of the functions are injective. Exactly 6 of the functions are surjective. No functions are both (since no functions here are injective).
0.4.2
Solution There are 9 functions: you have a choice of three outputs for \(f(1)\text{,}\) and for each, you have three choices for the output \(f(2)\text{.}\) Of these functions, 6 are injective, 0 are surjective, and 0 are both:
0.4.5
Solution
0.4.6
Solution
0.4.7
Solution Part (a) proves that \(f\) is not injective. The output 3 is assigned to 10 different inputs. Part (b) proves that \(f\) is not surjective. There is an element of the codomain (28) which is not assigned to any inputs.
0.4.8
Solution
0.4.9
Solution \(X\) can really be any set, as long as \(f(x) = 0\) or \(f(x) = 1\) for every \(x \in X\text{.}\) For example, \(X = \N\) and \(f(n) = 0\) works.
0.4.13
Solution \(f\) is injective. Let \(x\) and \(y\) be elements of the domain \(\Z\text{.}\) Assume \(f(x) = f(y)\text{.}\) If \(x\) and \(y\) are both even, then \(f(x) = x+1\) and \(f(y) = y+1\text{.}\) Since \(f(x) = f(y)\text{,}\) we have \(x + 1 = y + 1\) which implies that \(x = y\text{.}\) Similarly, if \(x\) and \(y\) are both odd, then \(x - 3 = y-3\) so again \(x = y\text{.}\) The only other possibility is that \(x\) is even an \(y\) is odd (or visa-versa). But then \(x + 1\) would be odd and \(y - 3\) would be even, so it cannot be that \(f(x) = f(y)\text{.}\) Therefore if \(f(x) = f(y)\) we then have \(x = y\text{,}\) which proves that \(f\) is injective. \(f\) is surjective. Let \(y\) be an element of the codomain \(\Z\text{.}\) We will show there is an element \(n\) of the domain (\(\Z\)) such that \(f(n) = y\text{.}\) There are two cases: First, if \(y\) is even, then let \(n = y+3\text{.}\) Since \(y\) is even, \(n\) is odd, so \(f(n) = n-3 = y+3-3 = y\) as desired. Second, if \(y\) is odd, then let \(n = y-1\text{.}\) Since \(y\) is odd, \(n\) is even, so \(f(n) = n+1 = y-1+1 = y\) as needed. Therefore \(f\) is surjective.
Proof
Proof
0.4.14
Solution Yes, this is a function, if you choose the domain and codomain correctly. The domain will be the set of students, and the codomain will be the set of possible grades. The function is almost certainly not injective, because it is likely that two students will get the same grade. The function might be surjective – it will be if there is at least one student who gets each grade.
0.4.16
Solution This cannot be a function. If the domain were the set of cards, then it is not a function because not every card gets dealt to a player. If the domain were the set of players, it would not be a function because a single player would get mapped to multiple cards. Since this is not a function, it doesn't make sense to say whether it is injective/surjective/bijective.
Solutions for Section 1.1
1.1.1
Solution There are 255 outfits. Use the multiplicative principle.
1.1.2
Solution 8 ties. Use the additive principle.
1.1.3
Solution For example, 16 is the number of choices you have if you want to watch one movie, either a comedy or horror flick. For example, 63 is the number of choices you have if you will watch two movies, first a comedy and then a horror.
1.1.5
Solution
1.1.6
Solution \(\card{A \cup B} + \card{A \cap B} = 13\text{.}\) Use PIE: we know \(\card{A \cup B} = 8 + 5 - \card{A \cap B}\text{.}\)
1.1.7
Answer 39 students. Use PIE or a Venn diagram.
1.1.11
Solution \(8 \cdot 8 =64\) words: you need to select the 4th and 5th letters.
Solutions for Section 1.2
1.2.1
Solution
1.2.2
Solution
1.2.5
Solution We can think of each row as a 6-bit string of weight 3 (since of the 6 coins, we require 3 to be pennies). Thus there are \({6 \choose 3} = 20\) rows possible. Each row requires 6 coins, so if we want to make all the rows at the same time, we will need 120 coins (60 of each). Now there are \(2^6 = 64\) rows possible, which is also \({6 \choose 0} + {6\choose 1} + {6 \choose 2} + {6 \choose 3} + {6 \choose 4} + {6 \choose 5} + {6 \choose 6}\text{,}\) if you break them up into rows containing 0, 1, 2, etc. pennies. Thus we need \(6 \cdot 64 = 384\) coins (192 of each).
1.2.6
Solution \({10 \choose 6} + {10\choose 7} + {10\choose 8} + {10 \choose 9} + {10\choose 10} = 386\) strings. Count the number of strings with each permissible number of 1's separately, then add them up.
1.2.8
Solution To get an \(x^{12}\text{,}\) we must pick 12 of the 15 factors to contribute an \(x\text{,}\) leaving the other 3 to contribute a 2. There are \({15 \choose 12}\) ways to select these 12 factors. So the term containing an \(x^{12}\) will be \({15 \choose 12}x^{12}2^{3}\text{.}\) In other words, the coefficient of \(x^{12}\) is \({15\choose 12}2^3 = 3640\text{.}\)
1.2.10
Solution
Solutions for Section 1.3
1.3.1
Solution
1.3.2
Solution Despite its name, we are not looking for a combination here. The order in which the three numbers appears matters. There are \(P(40,3) = 40\cdot 39 \cdot 38\) different possibilities for the "combination". This is assuming you cannot repeat any of the numbers (if you could, the answer would be \(40^3\)).
1.3.5
Solution \({7\choose 2}{7\choose 2} = 441\) quadrilaterals. We must pick two of the seven dots from the top row and two of the seven dots on the bottom row. However, it does not make a difference which of the two (on each row) we pick first because once these four dots are selected, there is exactly one quadrilateral that they determine.
1.3.6
Solution 5 squares. You need to skip exactly one dot on the top and on the bottom to make the side lengths equal. Once you pick a dot on the top, the other three dots are determined. This is tricky since you need to worry about running out of space. One way to count: break into cases by the location of the top left corner. You get \({7 \choose 2} + ({7 \choose 2}-1) + ({7 \choose 2} - 3) + ({7 \choose 2} - 6) + ({7 \choose 2} - 10) + ({7 \choose 2} - 15) = 91\) parallelograms. All of them \({7\choose 2}{7\choose 2} - \left[ {7 \choose 2} + ({7 \choose 2}-1) + ({7 \choose 2} - 3) + ({7 \choose 2} - 6) + ({7 \choose 2} - 10) + ({7 \choose 2} - 15) \right]\text{.}\) All of them, except the parallelograms.
1.3.8
Solution After the first letter (a), we must rearrange the remaining 7 letters. There are only two letters (s and e), so this is really just a bit-string question (think of s as 1 and e as 0). Thus there \({7 \choose 2} = 21\) anagrams starting with "a".
1.3.10
Solution
1.3.11
Solution \(9!\) (there are 10 people seated around the table, but it does not matter where King Arthur sits, only who sits to his left, two seats to his left, and so on).
1.3.12
Solution
Solutions for Section 1.4
1.4.1
Solution Question: How many subsets of size \(k\) are there of the set \(\{1,2,\ldots, n\}\text{?}\) Answer 1: You must choose \(k\) out of \(n\) elements to put in the set, which can be done in \({n \choose k}\) ways. Answer 2: First count the number of \(k\)-element subsets of \(\{1,2,\ldots, n\}\) which contain the number \(n\text{.}\) We must choose \(k-1\) of the \(n-1\) other element to include in this set. Thus there are \({n-1\choose k-1}\) such subsets. We have not yet counted all the \(k\)-element subsets of \(\{1,2,\ldots, n\}\) though. In fact, we have missed exactly those subsets which do NOT contain \(n\text{.}\) To form one of these subsets, we need to choose \(k\) of the other \(n-1\) elements, so this can be done in \({n-1 \choose k}\) ways. Thus the answer to the question is \({n-1 \choose k-1} + {n-1 \choose k}\text{.}\) Since the two answers are both answers tot eh same question, they are equal, establishing the identity \({n\choose k} = {n-1 \choose k-1} + {n-1 \choose k}\text{.}\) Proof
1.4.2
Solution Question: How many 2-letter words start with a, b, or c and end with either y or z? Answer 1: There are two words that start with a, two that start with b, two that start with c, for a total of \(2+2+2\text{.}\) Answer 2: There are three choices for the first letter and two choices for the second letter, for a total of \(3 \cdot 2\text{.}\) Since the two answers are both answers to the same question, they are equal. Thus \(2 + 2 + 2 = 3\cdot 2\text{.}\) Proof
1.4.3
Solution Question: How many subsets of \(A = {1,2,3, \ldots, n+1}\) contain exactly two elements? Answer 1: We must choose 2 elements from \(n+1\) choices, so there are \({n+1 \choose 2}\) subsets. Answer 2: We break this question down into cases, based on what the larger of the two elements in the subset is. The larger element can't be 1, since we need at least one element smaller than it. Larger element is 2: there is 1 choice for the smaller element. Larger element is 3: there are 2 choices for the smaller element. Larger element is 4: there are 3 choices for the smaller element. And so on. When the larger element is \(n+1\text{,}\) there are \(n\) choices for the smaller element. Since each two element subset must be in exactly one of these cases, the total number of two element subsets is \(1 + 2 + 3 + \cdots + n\text{.}\) Answer 1 and answer 2 are both correct answers to the same question, so they must be equal. Therefore, Proof
1.4.4
Solution She has \({15 \choose 6}\) ways to select the 6 bridesmaids, and then for each way, has 6 choices for the maid of honor. Thus she has \({15 \choose 6}6\) choices. She has 15 choices for who will be her maid of honor. Then she needs to select 5 of the remaining 14 friends to be bridesmaids, which she can do in \({14 \choose 5}\) ways. Thus she has \(15 {14 \choose 5}\) choices. We have answered the question (how many wedding parties can the bride choose from) in two ways. The first way gives the left-hand side of the identity and the second way gives the right-hand side of the identity. Therefore the identity holds.
1.4.5
Solution Question: You have a large container filled with ping-pong balls, all with a different number on them. You must select \(k\) of the balls, putting two of them in a jar and the others in a box. How many ways can you do this? Answer 1: First select 2 of the \(n\) balls to put in the jar. Then select \(k-2\) of the remaining \(n-2\) balls to put in the box. The first task can be completed in \({n \choose 2}\) different ways, the second task in \({n-2 \choose k-2}\) ways. Thus there are \({n \choose 2}{n-2 \choose k-2}\) ways to select the balls. Answer 2: First select \(k\) balls from the \(n\) in the container. Then pick 2 of the \(k\) balls you picked to put in the jar, placing the remaining \(k-2\) in the box. The first task can be completed in \({n \choose k}\) ways, the second task in \({k \choose 2}\) ways. Thus there are \({n \choose k}{k \choose 2}\) ways to select the balls. Since both answers count the same thing, they must be equal and the identity is established. Proof
1.4.6
Solution After the 1, we need to find a 5-bit string with one 1. There are \({5 \choose 1}\) ways to do this. Yes. We still need strings starting with 0001 (there are \({2 \choose 1}\) of these) and strings starting 00001 (there is only \({1 \choose 1} = 1\) of these). An example of the Hockey Stick Theorem:
1.4.7
Solution There are \({n \choose 1}\) places to put the non-2 digit. That digit can be either a 0 or a 1, so there are \(2{n \choose 1}\) such strings. We must choose two slots to fill with 0's or 1's. There are \({n \choose 2}\) ways to do that. Once the slots are picked, we have two choices for the first slot (0 or 1) and two choices for the second slot (0 or 1). So there are a total of \(2^2{n \choose 2}\) such strings. There are \({n \choose k}\) ways to pick which slots don't have the 2's. Then those slots can be filled in \(2^k\) ways (0 or 1 for each slot). So there are \(2^k{n \choose k}\) such strings. These strings contain just 0's and 1's, so they are bit strings. There are \(2^n\) bit strings. But keeping with the pattern above, we might write this as \(2^n {n \choose n}\) strings. We answer the question of how many length \(n\) ternary digit strings there are in two ways. First, each digit can be one of three choices, so the total number of strings is \(3^n\text{.}\) On the other hand, we could break the question down into cases by how many of the digits are 2's. If they are all 2's, then there are \({n \choose 0}\) strings. If all but one is a 2, then there are \(2{n \choose 1}\) strings. If all but 2 of the digits are 2's, then there are \(2^2{n \choose 2}\) strings. We choose 2 of the \(n\) digits to be non-2, and then there are 2 choices for each of those digits. And so on for every possible number of 2's in the string. Therefore \({n \choose 0} + 2{n \choose 1} + 2^2{n \choose 2} + 2^3{n \choose 3} + \cdots + 2^n{n \choose n} = 3^n. \)
1.4.8
Solution The word contains 9 letters: 3 "r"s, 2 "a"s and 2 "e"s, along with an "n" and a "g". We could first select the positions for the "r"s in \({9 \choose 3}\) ways, then the "a"s in \({6 \choose 2}\) ways, the "e"s in \({4 \choose 2}\) ways and then select one of the remaining two spots to put the "n" (placing the "g" in the last spot). This gives the answer Alternatively, we could select the positions of the letters in the opposite order, which would give an answer (where the 3 "r"s go in the remaining 3 spots). These two expressions are equal:
1.4.9
Solution Question: How many \(k\)-letter words can you make using \(n\) different letters without repeating any letter? Answer 1: There are \(n\) choices for the first letter, \(n-1\) choices for the second letter, \(n-2\) choices for the third letter, and so on until \(n - (k-1)\) choices for the \(k\)th letter (since \(k-1\) letters have already been assigned at that point). The product of these numbers can be written \(\frac{n!}{(n-k)!}\) which is \(P(n,k)\text{.}\) Therefore there are \(P(n,k)\) words. Answer 2: First pick \(k\) letters to be in the word from the \(n\) choices. This can be done in \({n \choose k}\) ways. Now arrange those letters into a word. There are \(k\) choices for the first letter, \(k-1\) choices for the second, and so on, for a total of \(k!\) arrangements of the \(k\) letters. Thus the total number of words is \({n \choose k}k!\text{.}\) Since the two answers are correct answers to the same question, we have established that \(P(n,k) = {n \choose k}k!\text{.}\) Proof
1.4.10
Solution Question: How many 5-element subsets are there of the set \(\{1,2,\ldots, n+3\}\text{.}\) Answer 1: We choose 5 out of the \(n+3\) elements, so \({n+3 \choose 5}\) subsets. Answer 2: Break this up into cases by what the "middle" (third smallest) element of the 5 element subset is. The smallest this could be is a 3. In that case, we have \({2 \choose 2}\) choices for the numbers below it, and \({n \choose 2}\) choices for the numbers above it. Alternatively, the middle number could be a 4. In this case there are \({3 \choose 2}\) choices for the bottom two numbers and \({n-1 \choose 2}\) choices for the top two numbers. If the middle number is 5, then there are \({4 \choose 2}\) choices for the bottom two numbers and \({n-2 \choose 2}\) choices for the top two numbers. An so on, all the way up to the largest the middle number could be, which is \(n+1\text{.}\) In that case there are \({n \choose 2}\) choices for the bottom two numbers and \({2 \choose 2}\) choices for the top number. Thus the number of 5 element subsets is Since the two answers correctly answer the same question, we have Proof
Solutions for Section 1.5
1.5.1
Solution Use stars and bars: each star represents one of the 5 elements of the set, each bar represents a switch between digits. So there are 5 stars and 9 bars, giving us \({14 \choose 9}\) sets.
1.5.2
Solution You take 3 strawberry, 1 lime, 0 licorice, 2 blueberry and 0 bubblegum. This is backwards. We don't want the stars to represent the kids because the kids are not identical, but the stars are. Instead we should use 5 stars (for the lollipops) and use 5 bars to switch between the 6 kids. For example, would represent the outcome with the first kid getting 2 lollipops, the third kid getting 3, and the rest of the kids getting none. This is the word AAAEOO. This doesn't represent a solution. Each star should represent one of the 6 units that add up to 6, and the bars should switch between the different variables. We have one too many bars. An example of a correct diagram would be representing that \(x_1 = 1\text{,}\) \(x_2 = 2\text{,}\) \(x_3 = 0\text{,}\) and \(x_4 = 3\text{.}\)
1.5.3
Solution
1.5.4
Solution
1.5.5
Solution There are \({7 \choose 5}\) numbers. We simply choose five of the seven digits and once chosen put them in increasing order. This requires stars and bars. Use a star to represent each of the 5 digits in the number, and use their position relative to the bars to say what numeral fills that spot. So we will have 5 stars and 6 bars, giving \({11 \choose 6}\) numbers.
1.5.11
Solution
Solutions for Section 1.6
1.6.1
Solution
1.6.3
Solution \({18 \choose 4} - \left[ {5 \choose 1}{11 \choose 4} - {5 \choose 2}{4 \choose 4}\right]\text{.}\) Subtract all the distributions for which one or more bins contain 7 or more balls.
1.6.4
Solution The easiest way to solve this is to instead count the solutions to \(y_1 + y_2 + y_3 + y_4 = 7\) with \(0 \le y_i \le 3\text{.}\) By taking \(x_i = y_i+2\text{,}\) each solution to this new equation corresponds to exactly one solution to the original equation. Now all the ways to distribute the 7 units to the four \(y_i\) variables can be found using stars and bars, specifically 7 stars and 3 bars, so \({10 \choose 3}\) ways. But this includes the ways that one or more \(y_i\) variables can be assigned more than 3 units. So subtract, using PIE. We get The \({4 \choose 1}\) counts the number of ways to pick one variable to be over-assigned, the \({6 \choose 3}\) is the number of ways to assign the remaining 3 units to the 4 variables. Note that this is the final answer because it is not possible to have two variables both get 4 units.
1.6.7
Solution The 9 derangements are: 2143, 2341, 2413, 3142, 3412, 3421, 4123, 4312, 4321.
1.6.8
Solution First pick one of the five elements to be fixed. For each such choice, derange the remaining four, using the standard advanced PIE formula. We get \({5 \choose 1}\left( 4! - \left[{4 \choose 1}3! - {4 \choose 2}2! + {4 \choose 3} 1! - {4 \choose 4} 0!\right] \right)\) permutations.
1.6.11
Solution There are \(5 \cdot 6^3\) functions for which \(f(1) \ne a\) and another \(5 \cdot 6^3\) functions for which \(f(2) \ne b\text{.}\) There are \(5^2 \cdot 6^2\) functions for which both \(f(1) \ne a\) and \(f(2) \ne b\text{.}\) So the total number of functions for which \(f(1) \ne a\) or \(f(2) \ne b\) or both is
1.6.12
Solution \(5^{10} - \left[{5 \choose 1}4^{10} - {5 \choose 2}3^{10} + {5 \choose 3}2^{10} - {5 \choose 4}1^{10}\right]\) functions. The \(5^{10}\) is all the functions from \(A\) to \(B\text{.}\) We subtract those that aren't surjective. Pick one of the five elements in \(B\) to not have in the range (in \({5 \choose 1}\) ways) and count all those functions (\(4^{10}\)). But this overcounts the functions where two elements from \(B\) are excluded from the range, so subtract those. And so on, using PIE.
Solutions for Section 1.7
1.7.1
Solution
1.7.2
Solution Neither. \({14 \choose 4}\) paths. Neither. Assuming you will wear each of the 4 ties on just 4 of the 7 days, without repeats: \({10\choose 4}P(7,4)\text{.}\) Neither. Since you could repeat letters: \(10^4\text{.}\) If no repeats are allowed, it would be \(P(10,4)\text{.}\) Neither. Actually, "k" is the 11th letter of the alphabet, so the answer is 0. If "k" was among the first 10 letters, there would only be 1 way - write it down. Neither. Either \({9\choose 3}\) (if every kid gets an apple) or \({13 \choose 3}\) (if appleless kids are allowed). Neither. Note that this could not be \({10 \choose 4}\) since the 10 things and 4 things are from different groups. \(4^{10}\text{.}\) Neither. \(16^{10}\) (each kid chooses yes or no to 4 varieties). Neither. 0. Neither. \(4^{10} - [{4\choose 1}3^{10} - {4\choose 2}2^{10} + {4 \choose 3}1^{10}]\text{.}\) Neither. \(10\cdot 4\text{.}\) Neither. \(4^{10}\text{.}\) Neither. If all the kids were identical, and you wanted no empty teams, it would be \({10 \choose 4}\text{.}\) Instead, this will be the same as the number of surjective functions from a set of size 11 to a set of size 5. Neither. \(4!\text{.}\) Neither. It's \({10 \choose 4}\) if you won't repeat any choices. If repetition is allowed, then this becomes \(x_1 + x_2 + \cdots +x_{10} = 4\text{,}\) which has \({13 \choose 9}\) solutions in non-negative integers. Neither. Since repetition of cookie type is allowed, the answer is \(10^4\text{.}\) Without repetition, you would have \(P(10,4)\text{.}\) Neither. It will be a complicated (possibly PIE) counting problem.
1.7.3
Solution You have 7 choices for regular ties (the 8 choices less the "no regular tie" option) and 31 choices for bow ties (32 total minus the "no bow tie" option). Thus total you have \(7 \cdot 31 = 217\) choices. Select one of the 3 bow ties to go on top. There are then 4 choices for the next tie, 3 for the tie after that, and so on. Thus \(3\cdot 4! = 72\) choices.
1.7.4
Solution You own 8 purple bow ties, 3 red bow ties, 3 blue bow ties and 5 green bow ties. How many ways can you select one of each color bow tie to take with you on a trip? \(8 \cdot 3 \cdot 3 \cdot 5\) ways. How many choices do you have for a single bow tie to wear tomorrow? \(8 + 3 + 3 + 5\) choices.
1.7.5
Solution We need 3 or more even digits. 3 even digits: \({5 \choose 3}2^3 2^2\text{.}\) 4 even digits: \({5 \choose 4}2^4 2\text{.}\) 5 even digits: \({5 \choose 5}2^5\text{.}\) So all together: \({5 \choose 3}2^3 2^2 + {5 \choose 4}2^4 2 + {5 \choose 5}2^5\) numbers.
1.7.6
Answer 51 passengers.
1.7.7
Solution There is a bijection between subsets and bit strings: a 1 means that element in is the subset, a 0 means that element is not in the subset. To get a subset of an 8 element set we have a 8-bit string. To make sure the subset contains exactly 5 elements, there must be 5 1's, so the weight must be 5.
1.7.8
Solution \({13 \choose 10} + {17 \choose 8}\text{.}\)
1.7.9
Solution With repeated letters allowed: \({8 \choose 5}5^5 21^3\) words. Without repeats: \({8 \choose 5}5! P(21, 3)\) words.
1.7.10
Solution
1.7.11
Solution \({18 \choose 8}\left({18 \choose 8} - 1\right)\) routes.
1.7.12
Solution \(2^7 + 2^7 - 2^4\) strings (using PIE).
1.7.13
Solution \({7 \choose 3} + {7 \choose 4} - {4 \choose 1}\) strings.
1.7.14
Solution (a) \(6! - 4\cdot 3!\) words. (b) \(6! - {6 \choose 3}3!\) words.
1.7.15
Solution \(2^n\) is the number of lattice paths which have length \(n\text{,}\) since for each step you can go up or right. Such a path would end along the line \(x + y = n\text{.}\) So you will end at \((0,n)\text{,}\) or \((1,n-1)\) or \((2, n-2)\) or … or \((n,0)\text{.}\) Counting the paths to each of these points separately, give \({n \choose 0}\text{,}\) \({n \choose 1}\text{,}\) \({n \choose 2}\text{,}\) …, \({n \choose n}\) (each time choosing which of the \(n\) steps to be to the right). These two methods count the same quantity, so are equal.
1.7.16
Answer
1.7.17
Solution
1.7.18
Solution \(4^6 - \left[{4 \choose 1}3^6 - {4 \choose 2}2^6 + {4 \choose 3} 1^6 \right]\text{.}\)
1.7.19
Solution
1.7.20
Solution You are giving your professor 4 types of cookies coming from 10 different types of cookies. This does not lend itself well to a function interpretation. We could say that the domain contains the 4 types you will give your professor and the codomain contains the 10 you can choose from, but then counting injections would be too much (it doesn't matter if you pick type 3 first and type 2 second, or the other way around, just that you pick those two types). We want to consider injective functions from the set \(\{\)most, second most, second least, least\(\}\) to the set of 10 cookie types. We want injections because we cannot pick the same type of cookie to give most and least of (for example). This is not a good problem to interpret as a function. The problem is that the domain would have to be the 12 cookies you bake, but these elements are indistinguishable (there is not a first cookie, second cookie, etc.). The domain should be the 12 shapes, the codomain the 10 types of cookies. Since we can use the same type for different shapes, we are interested in counting all functions here. Here we insist that each type of cookie be given at least once, so now we are asking for the number of surjections of those functions counted in the previous part.
Solutions for Section 2.1
2.1.1
Solution
2.1.3
Solution
2.1.4
Solution The sequences all have the same recurrence relation: \(a_n = a_{n-1} + a_{n-2}\) (the same as the Fibonacci numbers). The only difference is the initial conditions.
Solutions for Section 2.2
2.2.1
Solution Yes, since \(2013 = 5 + 4(503-1)\) (so \(a_{503} = 2013\)). 133
2.2.2
Solution \(32\text{,}\) which is \(26+6\text{.}\)
2.2.3
Solution 36.
2.2.4
Solution
2.2.5
Solution \(68117\text{.}\) If we take \(a_0 = 5\text{,}\) the terms of the sum are an arithmetic sequence with closed formula \(a_n = 5+2n\text{.}\) Then \(521 = a_{258}\text{,}\) for a total of 259 terms in the sum. Reverse and add to get 259 identical 526 terms, which is twice the total we seek. \(526\cdot 259 = 68117\)
2.2.6
Solution \(\frac{5-5\cdot 3^{21}}{-2}\text{.}\) Let the sum be \(S\text{,}\) and compute \(S - 3S = -2S\text{,}\) which causes terms except \(5\) and \(-5\cdot 3^{21}\) to cancel. Then solve for \(S\text{.}\)
2.2.10
Solution We have \(2 = 2\text{,}\) \(7 = 2+5\text{,}\) \(15 = 2 + 5 + 8\text{,}\) \(26 = 2+5+8+11\text{,}\) and so on. The terms in the sums are given by the arithmetic sequence \(b_n = 2+3n\text{.}\) In other words, \(a_n = \sum_{k=0}^n (2+3k)\text{.}\) To find the closed formula, we reverse and add. We get \(a_n = \frac{(4+3n)(n+1)}{2}\) (we have \(n+1\) there because there are \(n+1\) terms in the sum for \(a_n\)).
2.2.12
Solution
2.2.13
Solution
Solutions for Section 2.3
2.3.1
Solution Notice that the third differences are constant, so \(a_n = an^3 + bn^2 + cn + d\text{.}\) Use the terms of the sequence to solve for \(a, b, c,\) and \(d\) to get \(a_n = \frac{1}{6} (12+11 n+6 n^2+n^3)\text{.}\)
2.3.3
Solution The first differences are \(2, 4, 6, 8, \ldots\text{,}\) and the second differences are \(2, 2, 2, \ldots\text{.}\) Thus the original sequence is \(\Delta^2\)-constant, so can be fit to a quadratic. Call the original sequence \(a_n\text{.}\) Consider \(a_n - n^2\text{.}\) This gives \(0, -1, -2, -3, \ldots\text{.}\) That sequence has closed formula \(1-n\) (starting at \(n = 1\)) so we have \(a_n - n^2 = 1-n\) or equivalently \(a_n = n^2 - n + 1\text{.}\)
2.3.6
Solution \(a_{n-1} = (n-1)^2 + 3(n-1) + 4 = n^2 + n + 2\text{.}\) Thus \(a_n - a_{n-1} = 2n+2\text{.}\) Note that this is linear (arithmetic). We can check that we are correct. The sequence \(a_n\) is \(4, 8, 14, 22, 32, \ldots\) and the sequence of differences is thus \(4, 6, 8, 10,\ldots\) which agrees with \(2n+2\) (if we start at \(n = 1\)).
Solutions for Section 2.4
2.4.1
Solution 171 and 341. \(a_n = a_{n-1} + 2a_{n-2}\) with \(a_0 = 3\) and \(a_1 = 5\text{.}\) Closed formula: \(a_n = \frac{8}{3}2^n + \frac{1}{3}(-1)^n\text{.}\) To find this solve the characteristic polynomial, \(x^2 - x - 2\text{,}\) to get characteristic roots \(x = 2\) and \(x=-1\text{.}\) Then solve the system
2.4.2
Solution \(a_n = 3 + 2^{n+1}\text{.}\) We should use telescoping or iteration here. For example, telescoping gives which sums to \(a_n - a_0 = 2^{n+1} - 2\) (using the multiply-shift-subtract technique from Section 2.2 for the right-hand side). Substituting \(a_0 = 5\) and solving for \(a_n\) completes the solution.
2.4.3
Solution We claim \(a_n = 4^n\) works. Plug it in: \(4^n = 3(4^{n-1}) + 4(4^{n-2})\text{.}\) This works - just simplify the right-hand side.
2.4.4
Solution By the Characteristic Root Technique. \(a_n = 4^n + (-1)^n\text{.}\)
Solutions for Section 2.5
2.5.1
Solution We must prove that \(1 + 2 + 2^2 + 2^3 + \cdots +2^n = 2^{n+1} - 1\) for all \(n \in \N\text{.}\) Thus let \(P(n)\) be the statement \(1 + 2 + 2^2 + \cdots + 2^n = 2^{n+1} - 1\text{.}\) We will prove that \(P(n)\) is true for all \(n \in \N\text{.}\) First we establish the base case, \(P(0)\text{,}\) which claims that \(1 = 2^{0+1} -1\text{.}\) Since \(2^1 - 1 = 2 - 1 = 1\text{,}\) we see that \(P(0)\) is true. Now for the inductive case. Assume that \(P(k)\) is true for an arbitrary \(k \in \N\text{.}\) That is, \(1 + 2 + 2^2 + \cdots + 2^k = 2^{k+1} - 1\text{.}\) We must show that \(P(k+1)\) is true (i.e., that \(1 + 2 + 2^2 + \cdots + 2^{k+1} = 2^{k+2} - 1\)). To do this, we start with the left-hand side of \(P(k+1)\) and work to the right-hand side: Thus \(P(k+1)\) is true so by the principle of mathematical induction, \(P(n)\) is true for all \(n \in \N\text{.}\) Proof
2.5.2
Solution Let \(P(n)\) be the statement "\(7^n - 1\) is a multiple of 6." We will show \(P(n)\) is true for all \(n \in \N\text{.}\) First we establish the base case, \(P(0)\text{.}\) Since \(7^0 - 1 = 0\text{,}\) and \(0\) is a multiple of 6, \(P(0)\) is true. Now for the inductive case. Assume \(P(k)\) holds for an arbitrary \(k \in \N\text{.}\) That is, \(7^k - 1\) is a multiple of 6, or in other words, \(7^k - 1 = 6j\) for some integer \(j\text{.}\) Now consider \(7^{k+1} - 1\text{:}\) Therefore \(7^{k+1} - 1\) is a multiple of 6, or in other words, \(P(k+1)\) is true. Therefore by the principle of mathematical induction, \(P(n)\) is true for all \(n \in \N\text{.}\) Proof
2.5.3
Solution Let \(P(n)\) be the statement \(1+3 +5 + \cdots + (2n-1) = n^2\text{.}\) We will prove that \(P(n)\) is true for all \(n \ge 1\text{.}\) First the base case, \(P(1)\text{.}\) We have \(1 = 1^2\) which is true, so \(P(1)\) is established. Now the inductive case. Assume that \(P(k)\) is true for some fixed arbitrary \(k \ge 1\text{.}\) That is, \(1 + 3 + 5 + \cdots + (2k-1) = k^2\text{.}\) We will now prove that \(P(k+1)\) is also true (i.e., that \(1 + 3 + 5 + \cdots + (2k+1) = (k+1)^2\)). We start with the left-hand side of \(P(k+1)\) and work to the right-hand side: Thus \(P(k+1)\) holds, so by the principle of mathematical induction, \(P(n)\) is true for all \(n \ge 1\text{.}\) Proof
2.5.4
Solution Let \(P(n)\) be the statement \(F_0 + F_2 + F_4 + \cdots + F_{2n} = F_{2n+1} - 1\text{.}\) We will show that \(P(n)\) is true for all \(n \ge 0\text{.}\) First the base case is easy because \(F_0 = 0\) and \(F_1 = 1\) so \(F_0 = F_1 - 1\text{.}\) Now consider the inductive case. Assume \(P(k)\) is true, that is, assume \(F_0 + F_2 + F_4 + \cdots + F_{2k} = F_{2k+1} - 1\text{.}\) To establish \(P(k+1)\) we work from left to right: Therefore \(F_0 + F_2 + F_4 + \cdots + F_{2k+2} = F_{2k+3} - 1\text{,}\) which is to say \(P(k+1)\) holds. Therefore by the principle of mathematical induction, \(P(n)\) is true for all \(n \ge 0\text{.}\) Proof
2.5.5
Solution Let \(P(n)\) be the statement \(2^n \lt n!\text{.}\) We will show \(P(n)\) is true for all \(n \ge 4\text{.}\) First, we check the base case and see that yes, \(2^4 \lt 4!\) (as \(16 \lt 24\)) so \(P(4)\) is true. Now for the inductive case. Assume \(P(k)\) is true for an arbitrary \(k \ge 4\text{.}\) That is, \(2^k \lt k!\text{.}\) Now consider \(P(k+1)\text{:}\) \(2^{k+1} \lt (k+1)!\text{.}\) To prove this, we start with the left side and work to the right side. Therefore \(2^{k+1} \lt (k+1)!\) so we have established \(P(k+1)\text{.}\) Thus by the principle of mathematical induction \(P(n)\) is true for all \(n \ge 4\text{.}\) Proof
2.5.10
Solution The only problem is that we never established the base case. Of course, when \(n = 0\text{,}\) \(0+3 \ne 0+7\text{.}\)
2.5.11
Solution Let \(P(n)\) be the statement that \(n + 3 \lt n + 7\text{.}\) We will prove that \(P(n)\) is true for all \(n \in \N\text{.}\) First, note that the base case holds: \(0+3 \lt 0+7\text{.}\) Now assume for induction that \(P(k)\) is true. That is, \(k+3 \lt k+7\text{.}\) We must show that \(P(k+1)\) is true. Now since \(k + 3 \lt k + 7\text{,}\) add 1 to both sides. This gives \(k + 3 + 1 \lt k + 7 + 1\text{.}\) Regrouping \((k+1) + 3 \lt (k+1) + 7\text{.}\) But this is simply \(P(k+1)\text{.}\) Thus by the principle of mathematical induction \(P(n)\) is true for all \(n \in \N\text{.}\) Proof
2.5.12
Solution The problem here is that while \(P(0)\) is true, and while \(P(k) \imp P(k+1)\) for some values of \(k\text{,}\) there is at least one value of \(k\) (namely \(k = 99\)) when that implication fails. For a valid proof by induction, \(P(k) \imp P(k+1)\) must be true for all values of \(k\) greater than or equal to the base case.
2.5.13
Solution Let \(P(n)\) be the statement "there is a strictly increasing sequence \(a_1, a_2, \ldots, a_n\) with \(a_n \lt 100\text{.}\)" We will prove \(P(n)\) is true for all \(n \ge 1\text{.}\) First we establish the base case: \(P(1)\) says there is a single number \(a_1\) with \(a_1 \lt 100\text{.}\) This is true – take \(a_1 = 0\text{.}\) Now for the inductive step, assume \(P(k)\) is true. That is there exists a strictly increasing sequence \(a_1, a_2, a_3, \ldots, a_k\) with \(a_k \lt 100\text{.}\) Now consider this sequence, plus one more term, \(a_{k+1}\) which is greater than \(a_k\) but less than \(100\text{.}\) Such a number exists, for example, the average between \(a_k\) and 100. So then \(P(k+1)\) is true, so we have shown that \(P(k) \imp P(k+1)\text{.}\) Thus by the principle of mathematical induction, \(P(n)\) is true for all \(n \in \N\text{.}\) Proof
2.5.16
Solution The idea is to define the sequence so that \(a_n\) is less than the distance between the previous partial sum and 2. That way when you add it into the next partial sum, the partial sum is still less than 2. You could do this ahead of time, or use a clever \(P(n)\) in the induction proof. Let \(P(n)\) be the statement, "there is a sequence of positive real numbers \(a_0, a_1, a_2, \ldots, a_n\) such that \(a_0 + a_1 + a_2 + \cdots + a_n \lt 2\text{.}\)" Base case: Pick any \(a_0 \lt 2\text{.}\) Inductive case: Assume that \(a_1 + a_2 + \cdots + a_k \lt 2\text{.}\) Now let \(a_{k+1} = \frac{2- a_1 + a_2 + \cdots + a_k}{2}\text{.}\) Then \(a_1 + a_2 + \cdots +a_k + a_{k+1} \lt 2\text{.}\) Therefore, by the principle of mathematical induction, \(P(n)\) is true for all \(n \in \N\) Proof
2.5.17
Solution The proof will by by strong induction. Let \(P(n)\) be the statement "\(n\) is either a power of 2 or can be written as the sum of distinct powers of 2." We will show that \(P(n)\) is true for all \(n \ge 1\text{.}\) Base case: \(1 = 2^0\) is a power of 2, so \(P(1)\) is true. Inductive case: Suppose \(P(k)\) is true for all \(k \lt n\text{.}\) Now if \(n\) is a power of 2, we are done. If not, let \(2^x\) be the largest power of 2 strictly less than \(n\text{.}\) Consider \(n - 2^x\text{,}\) which is a smaller number, in fact smaller than both \(n\) and \(2^x\text{.}\) Thus \(n-2^x\) is either a power of 2 or can be written as the sum of distinct powers of 2, but none of them are going to be \(2^x\text{,}\) so the together with \(2^x\) we have written \(n\) as the sum of distinct powers of 2. Therefore, by the principle of (strong) mathematical induction, \(P(n)\) is true for all \(n \ge 1\text{.}\) Proof
2.5.19
Solution Note, we have already proven this without using induction, but looking at it inductively sheds light onto the problem (and is fun). Let \(P(n)\) be the statement "when \(n\) people shake hands with each other, there are a total of \(\frac{n(n-1)}{2}\) handshakes." Base case: When \(n=2\text{,}\) there will be one handshake, and \(\frac{2(2-1)}{2} = 1\text{.}\) Thus \(P(2)\) is true. Inductive case: Assume \(P(k)\) is true for arbitrary \(k\ge 2\) (that the number of handshakes among \(k\) people is \(\frac{k(k-1)}{2}\text{.}\) What happens if a \(k+1\)st person shows up? How many new handshakes take place? The new person must shake hands with everyone there, which is \(k\) new handshakes. So the total is now \(\frac{k(k-1)}{2} + k = \frac{(k+1)k}{2}\text{,}\) as needed. Therefore, by the principle of mathematical induction, \(P(n)\) is true for all \(n \ge 2\text{.}\) Proof
2.5.20
Solution When \(n = 0\text{,}\) we get \(x^0 +\frac{1}{x^0} = 2\) and when \(n = 1\text{,}\) \(x + \frac{1}{x}\) is an integer, so the base case holds. Now assume the result holds for all natural numbers \(n \lt k\text{.}\) In particular, we know that \(x^{k-1} + \frac{1}{x^{k-1}}\) and \(x + \frac{1}{x}\) are both integers. Thus their product is also an integer. But, Note also that \(x^{k-2} + \frac{1}{x^{k-2}}\) is an integer by the induction hypothesis, so we can conclude that \(x^k + \frac{1}{x^k}\) is an integer.
2.5.23
Solution The idea here is that if we take the logarithm of \(a^n\text{,}\) we can increase \(n\) by 1 if we multiply by another \(a\) (inside the logarithm). This results in adding 1 more \(\log(a)\) to the total. Let \(P(n)\) be the statement \(\log(a^n) = n \log(a)\text{.}\) The base case, \(P(2)\) is true, because \(\log(a^2) = \log(a\cdot a) = \log(a) + \log(a) = 2\log(a)\text{,}\) by the product rule for logarithms. Now assume, for induction, that \(P(k)\) is true. That is, \(\log(a^k) = k\log(a)\text{.}\) Consider \(\log(a^{k+1})\text{.}\) We have with the last equality due to the inductive hypothesis. But this simplifies to \((k+1) \log(a)\text{,}\) establishing \(P(k+1)\text{.}\) Therefore by the principle of mathematical induction, \(P(n)\) is true for all \(n \ge 2\text{.}\) Proof
Solutions for Section 2.6
2.6.1
Solution \(\frac{430\cdot 107}{2} = 23005\text{.}\)
2.6.2
Solution
2.6.3
Solution
2.6.5
Solution \(a_n = n^2 + 4n - 1\text{.}\)
2.6.6
Solution The sequence of partial sums will be a degree 4 polynomial (its sequence of differences will be the original sequence). The sequence of second differences will be a degree 1 polynomial - an arithmetic sequence.
2.6.7
Solution No, taking differences gives the original sequence back, so the differences will never be constant.
2.6.8
Solution \(b_n = (n+3)n\text{.}\)
2.6.10
Solution
2.6.11
Solution
2.6.12
Solution On the first day, your 2 mini bunnies become 2 large bunnies. On day 2, your two large bunnies produce 4 mini bunnies. On day 3, you have 4 mini bunnies (produced by your 2 large bunnies) plus 6 large bunnies (your original 2 plus the 4 newly matured bunnies). On day 4, you will have \(12\) mini bunnies (2 for each of the 6 large bunnies) plus 10 large bunnies (your previous 6 plus the 4 newly matured). The sequence of total bunnies is \(2, 2, 6, 10, 22, 42\ldots\) starting with \(a_0 = 2\) and \(a_1 = 2\text{.}\) Using the characteristic root technique, we find \(a_n = a2^n + b(-1)^n\text{,}\) and we can find \(a\) and \(b\) to give \(a_n = \frac{4}{3}2^n + \frac{2}{3}(-1)^n\text{.}\)
2.6.13
Solution Hint: \((n+1)^{n+1} > (n+1) \cdot n^{n}\text{.}\) Hint: This should be similar to the other sum proofs. The last bit comes down to adding fractions. Hint: Write \(4^{k+1} - 1 = 4\cdot 4^k - 4 + 3\text{.}\) Hint: one 9-cent stamp is 1 more than two 4-cent stamps, and seven 4-cent stamps is 1 more than three 9-cent stamps. Careful to actually use induction here. The base case: \(2^2 = 4\text{.}\) The inductive case: assume \((2n)^2\) is divisible by 4 and consider \((2n+2)^2 = (2n)^2 + 4n + 4\text{.}\) This is divisible by 4 because \(4n +4\) clearly is, and by our inductive hypothesis, so is \((2n)^2\text{.}\)
2.6.14
Solution Hint: This is a straight forward induction proof. Note you will need to simplify \(\left(\frac{n(n+1)}{2}\right)^2 + (n+1)^3\) and get \(\left(\frac{(n+1)(n+2)}{2}\right)^2\text{.}\)
2.6.15
Solution Hint: there are two base cases \(P(0)\) and \(P(1)\text{.}\) Then, for the inductive case, assume \(P(k)\) is true for all \(k \lt n\text{.}\) This allows you to assume \(a_{n-1} = 1\) and \(a_{n-2} = 1\text{.}\) Apply the recurrence relation.
2.6.16
Solution Note that \(1 = 2^0\text{;}\) this is your base case. Now suppose \(k\) can be written as the sum of distinct powers of 2 for all \(1\le k \le n\text{.}\) We can then write \(n\) as the sum of distinct powers of 2 as follows: subtract the largest power of 2 less than \(n\) from \(n\text{.}\) That is, write \(n = 2^j + k\) for the largest possible \(j\text{.}\) But \(k\) is now less than \(n\text{,}\) and also less than \(2^j\text{,}\) so write \(k\) as the sum of distinct powers of 2 (we can do so by the inductive hypothesis). Thus \(n\) can be written as the sum of distinct powers of 2 for all \(n \ge 1\text{.}\)
2.6.17
Solution Let \(P(n)\) be the statement, "every set containing \(n\) elements has \(2^n\) different subsets." We will show \(P(n)\) is true for all \(n \ge 1\text{.}\) Base case: Any set with 1 element \(\{a\}\) has exactly 2 subsets: the empty set and the set itself. Thus the number of subsets is \(2= 2^1\text{.}\) Thus \(P(1)\) is true. Inductive case: Suppose \(P(k)\) is true for some arbitrary \(k \ge 1\text{.}\) Thus every set containing exactly \(k\) elements has \(2^k\) different subsets. Now consider a set containing \(k+1\) elements: \(A = \{a_1, a_2, \ldots, a_k, a_{k+1}\}\text{.}\) Any subset of \(A\) must either contain \(a_{k+1}\) or not. In other words, a subset of \(A\) is just a subset of \(\{a_1, a_2,\ldots, a_k\}\) with or without \(a_{k+1}\text{.}\) Thus there are \(2^k\) subsets of \(A\) which contain \(a_{k+1}\) and another \(2^{k+1}\) subsets of \(A\) which do not contain \(a^{k+1}\text{.}\) This gives a total of \(2^k + 2^k = 2\cdot 2^k = 2^{k+1}\) subsets of \(A\text{.}\) But our choice of \(A\) was arbitrary, so this works for any subset containing \(k+1\) elements, so \(P(k+1)\) is true. Therefore, by the principle of mathematical induction, \(P(n)\) is true for all \(n \ge 1\text{.}\)
Solutions for Section 3.1
3.1.1
Solution Hint: you should get three T's and one F. Only that there will be cake. It's NOT your birthday! It's your birthday, but the cake is a lie.
3.1.2
Solution
\(P\) \(Q\) \((P \vee Q) \imp (P \wedge Q)\) T T T T F F F T F F F T
3.1.3
Solution If the statement is true, then both \(P\) and \(Q\) are false.
\(P\) \(Q\) \(\neg P \wedge (Q \imp P)\) T T F T F F F T F F F T
3.1.5
Solution Make a truth table for each and compare. The statements are logically equivalent.
3.1.7
Answer \((P \wedge Q) \wedge (R \wedge \neg R)\text{.}\) This is necessarily false, so it is also equivalent to \(P \wedge \neg P\text{.}\) Either Sam is a woman and Chris is a man, or Chris is a woman.
3.1.10
Solution The deduction rule is valid. To see this, make a truth table which contains \(P \vee Q\) and \(\neg P\) (and \(P\) and \(Q\) of course). Look at the truth value of \(Q\) in each of the rows that have \(P \vee Q\) and \(\neg P\) true.
3.1.14
Solution There is a number \(n\) for which every other number is strictly greater than \(n\text{.}\) There is a number \(n\) which is not between any other two numbers.
Solutions for Section 3.2
3.2.1
Solution For all integers \(a\) and \(b\text{,}\) if \(a\) or \(b\) is not even, then \(a+b\) is not even. For all integers \(a\) and \(b\text{,}\) if \(a\) and \(b\) are even, then \(a+b\) is even. There are numbers \(a\) and \(b\) such that \(a+b\) is even but \(a\) and \(b\) are not both even. False. For example, \(a = 3\) and \(b = 5\text{.}\) \(a+b = 8\text{,}\) but neither \(a\) nor \(b\) are even. False, since it is equivalent to the original statement. True. Let \(a\) and \(b\) be integers. Assume both are even. Then \(a = 2k\) and \(b = 2j\) for some integers \(k\) and \(j\text{.}\) But then \(a+b = 2k + 2j = 2(k+j)\) which is even. True, since the statement is false.
3.2.2
Solution Direct proof. Let \(n\) be an integer. Assume \(n\) is even. Then \(n = 2k\) for some integer \(k\text{.}\) Thus \(8n = 16k = 2(8k)\text{.}\) Therefore \(8n\) is even. The converse is false. That is, there is an integer \(n\) such that \(8n\) is even but \(n\) is odd. For example, consider \(n = 3\text{.}\) Then \(8n = 24\) which is even but \(n = 3\) is odd.
Proof
3.2.6
Solution Suppose \(\sqrt{3}\) were rational. Then \(\sqrt{3} = \frac{a}{b}\) for some integers \(a\) and \(b \ne 0\text{.}\) Without loss of generality, assume \(\frac{a}{b}\) is reduced. Now So \(a^2\) is a multiple of 3. This can only happen if \(a\) is a multiple of 3, so \(a = 3k\) for some integer \(k\text{.}\) Then we have So \(b^2\) is a multiple of 3, making \(b\) a multiple of 3 as well. But this contradicts our assumption that \(\frac{a}{b}\) is in lowest terms. Therefore, \(\sqrt{3}\) is irrational. Proof
3.2.8
Solution We will prove the contrapositive: if \(n\) is even, then \(5n\) is even. Let \(n\) be an arbitrary integer, and suppose \(n\) is even. Then \(n = 2k\) for some integer \(k\text{.}\) Thus \(5n = 5\cdot 2k = 10k = 2(5k)\text{.}\) Since \(5k\) is an integer, we see that \(5n\) must be even. This completes the proof. Proof
3.2.11
Solution This is an example of the pigeonhole principle. We can prove it by contrapositive. Suppose that each number only came up 6 or fewer times. So there are at most six 1's, six 2's, and so on. That's a total of 36 dice, so you must not have rolled all 40 dice. We can have 9 dice without any four matching or any four being all different: three 1's, three 2's, three 3's. We will prove that whenever you roll 10 dice, you will always get four matching or all being different. Suppose you roll 10 dice, but that there are NOT four matching rolls. This means at most, there are three of any given value. If we only had three different values, that would be only 9 dice, so there must be 4 different values, giving 4 dice that are all different.
Proof
Proof
3.2.12
Solution We give a proof by contradiction. Suppose, contrary to stipulation that \(\log(7)\) is rational. Then \(\log(7) = \frac{a}{b}\) with \(a\) and \(b \ne 0\) integers. By properties of logarithms, this implies Equivalently, But this is impossible as any power of 7 will be odd while any power of 10 will be even. Therefore, \(\log(7)\) is irrational. Proof
3.2.15
Solution Proof by contradiction. Start of proof: Assume, for the sake of contradiction, that there are integers \(x\) and \(y\) such that \(x\) is a prime greater than 5 and \(x = 6y + 3\text{.}\) End of proof: … this is a contradiction, so there are no such integers. Direct proof. Start of proof: Let \(n\) be an integer. Assume \(n\) is a multiple of 3. End of proof: Therefore \(n\) can be written as the sum of consecutive integers. Proof by contrapositive. Start of proof: Let \(a\) and \(b\) be integers. Assume that \(a\) and \(b\) are even. End of proof: Therefore \(a^2 + b^2\) is even.
Solutions for Section 3.3
3.3.1
Solution
\(P\) \(Q\) \(R\) \(\neg P \imp (Q \wedge R)\) T T T T T T F T T F T T T F F T F T T T F T F F F F T F F F F F
3.3.2
Solution Peter is not tall and Robert is not skinny. You must be in row 6 in the truth table above.
3.3.3
Solution Yes. To see this, make a truth table for each statement and compare.
3.3.4
Solution Make a truth table that includes all three statements in the argument: Notice that in every row for which both \(P \imp Q\) and \(P \imp R\) is true, so is \(P \imp (Q \wedge R)\text{.}\) Therefore, whenever the premises of the argument are true, so is the conclusion. In other words, the deduction rule is valid.
\(P\) \(Q\) \(R\) \(P \imp Q\) \(P \imp R\) \(P \imp (Q \wedge R)\) T T T T T T T T F T F F T F T F T F T F F F F F F T T T T T F T F T T T F F T T T T F F F T T T
3.3.5
Solution Negation: The power goes off and the food does not spoil. Converse: If the food spoils, then the power went off. Contrapositive: If the food does not spoil, then the power did not go off. Negation: The door is closed and the light is on. Converse: If the light is off then the door is closed. Contrapositive: If the light is on then the door is open. Negation: \(\exists x (x \lt 1 \wedge x^2 \ge 1)\) Converse: \(\forall x( x^2 \lt 1 \imp x \lt 1)\) Contrapositive: \(\forall x (x^2 \ge 1 \imp x \ge 1)\text{.}\) Negation: There is a natural number \(n\) which is prime but not solitary. Converse: For all natural numbers \(n\text{,}\) if \(n\) is solitary, then \(n\) is prime. Contrapositive: For all natural numbers \(n\text{,}\) if \(n\) is not solitary then \(n\) is not prime. Negation: There is a function which is differentiable and not continuous. Converse: For all functions \(f\text{,}\) if \(f\) is continuous then \(f\) is differentiable. Contrapositive: For all functions \(f\text{,}\) if \(f\) is not continuous then \(f\) is not differentiable. Negation: There are integers \(a\) and \(b\) for which \(a\cdot b\) is even but \(a\) or \(b\) is odd. Converse: For all integers \(a\) and \(b\text{,}\) if \(a\) and \(b\) are even then \(ab\) is even. Contrapositive: For all integers \(a\) and \(b\text{,}\) if \(a\) or \(b\) is odd, then \(ab\) is odd. Negation: There are integers \(x\) and \(y\) such that for every integer \(n\text{,}\) \(x \gt 0\) and \(nx \le y\text{.}\) Converse: For every integer \(x\) and every integer \(y\) there is an integer \(n\) such that if \(nx > y\) then \(x > 0\text{.}\) Contrapositive: For every integer \(x\) and every integer \(y\) there is an integer \(n\) such that if \(nx \le y\) then \(x \le 0\text{.}\) Negation: There are real numbers \(x\) and \(y\) such that \(xy = 0\) but \(x \ne 0\) and \(y \ne 0\text{.}\) Converse: For all real numbers \(x\) and \(y\text{,}\) if \(x = 0\) or \(y = 0\) then \(xy = 0\) Contrapositive: For all real numbers \(x\) and \(y\text{,}\) if \(x \ne 0\) and \(y \ne 0\) then \(xy \ne 0\text{.}\) Negation: There is at least one student in Math 228 who does not understand implications but will still pass the exam. Converse: For every student in Math 228, if they fail the exam, then they did not understand implications. Contrapositive: For every student in Math 228, if they pass the exam, then they understood implications.
3.3.6
Solution The statement is true. If \(n\) is an even integer less than or equal to 7, then the only way it could not be negative is if \(n\) was equal to 0, 2, 4, or 6. There is an integer \(n\) such that \(n\) is even and \(n \le 7\) but \(n\) is not negative and \(n \not\in \{0,2,4,6\}\text{.}\) This is false, since the original statement is true. For all integers \(n\text{,}\) if \(n\) is not negative and \(n \not\in\{0,2,4,6\}\) then \(n\) is odd or \(n > 7\text{.}\) This is true, since the contrapositive is equivalent to the original statement (which is true). For all integers \(n\text{,}\) if \(n\) is negative or \(n \in \{0,2,4,6\}\) then \(n\) is even and \(n \le 7\text{.}\) This is false. \(n = -3\) is a counterexample.
3.3.7
Solution For any number \(x\text{,}\) if it is the case that adding any number to \(x\) gives that number back, then multiplying any number by \(x\) will give 0. This is true (of the integers or the reals). The "if" part only holds if \(x = 0\text{,}\) and in that case, anything times \(x\) will be 0. The converse in words is this: for any number \(x\text{,}\) if everything times \(x\) is zero, then everything added to \(x\) gives itself. Or in symbols: \(\forall x (\forall z (x \cdot z = 0) \imp \forall y (x + y = y))\text{.}\) The converse is true: the only number which when multiplied by any other number gives 0 is \(x = 0\text{.}\) And if \(x = 0\text{,}\) then \(x + y = y\text{.}\) The contrapositive in words is: for any number \(x\text{,}\) if there is some number which when multiplied by \(x\) does not give zero, then there is some number which when added to \(x\) does not give that number. In symbols: \(\forall x (\exists z (x\cdot z \ne 0) \imp \exists y (x + y \ne y))\text{.}\) We know the contrapositive must be true because the original implication is true. The negation: there is a number \(x\) such that any number added to \(x\) gives the number back again, but there is a number you can multiply \(x\) by and not get 0. In symbols: \(\exists x (\forall y (x + y = y) \wedge \exists z (x \cdot z \ne 0))\text{.}\) Of course since the original implication is true, the negation is false.
3.3.8
Solution If you have lost weight, then you exercised. If you exercise, then you will lose weight. If you are American, then you are patriotic. If you are patriotic, then you are American. If a number is rational, then it is real. If a number is not even, then it is prime. (Or the contrapositive: if a number is not prime, then it is even.) If the Broncos don't win the Super Bowl, then they didn't play in the Super Bowl. Alternatively, if the Broncos play in the Super Bowl, then they will win the Super Bowl.
3.3.9
Solution
3.3.10
Solution Direct proof. Let \(n\) be an integer. Assume \(n\) is odd. So \(n = 2k+1\) for some integer \(k\text{.}\) Then Since \(7k + 3\) is an integer, we see that \(7n\) is odd. The converse is: for all integers \(n\text{,}\) if \(7n\) is odd, then \(n\) is odd. We will prove this by contrapositive. Let \(n\) be an integer. Assume \(n\) is not odd. Then \(n = 2k\) for some integer \(k\text{.}\) So \(7n = 14k = 2(7k)\) which is to say \(7n\) is even. Therefore \(7n\) is not odd.
Proof
Proof
3.3.11
Solution Suppose you only had 5 coins of each denomination. This means you have 5 pennies, 5 nickels, 5 dimes and 5 quarters. This is a total of 20 coins. But you have more than 20 coins, so you must have more than 5 of at least one type. Suppose you have 22 coins, including \(2k\) nickels, \(2j\) dimes, and \(2l\) quarters (so an even number of each of these three types of coins). The number of pennies you have will then be But this says that the number of pennies is also even (it is 2 times an integer). Thus we have established the contrapositive of the statement, "If you have an odd number of pennies then you have an odd number of at least one other coin type." You need 10 coins. You could have 3 pennies, 3 nickels, and 3 dimes. The 10th coin must either be a quarter, giving you 4 coins that are all different, or else a 4th penny, nickel or dime. To prove this, assume you don't have 4 coins that are all the same or all different. In particular, this says that you only have 3 coin types, and each of those types can only contain 3 coins, for a total of 9 coins, which is less than 10.
Solutions for Section 4.1
4.1.1
Solution This is asking for the number of edges in \(K_{10}\text{.}\) Each vertex (person) has degree (shook hands with) 9 (people). So the sum of the degrees is \(90\text{.}\) However, the degrees count each edge (handshake) twice, so there are 45 edges in the graph. That is how many handshakes took place.
4.1.2
Solution It is possible for everyone to be friends with exactly 2 people. You could arrange the 5 people in a circle and say that everyone is friends with the two people on either side of them (so you get the graph \(C_5\)). However, it is not possible for everyone to be friends with 3 people. That would lead to a graph with an odd number of odd degree vertices which is impossible since the sum of the degrees must be even.
4.1.3
Solution Yes. For example, both graphs below contain 6 vertices, 7 edges, and have degrees (2,2,2,2,3,3). 
4.1.4
Solution The graphs are not equal. For example, graph 1 has an edge \(\{a,b\}\) but graph 2 does not have that edge. They are isomorphic. One possible isomorphism is \(f:G_1 \to G_2\) defined by \(f(a) = d\text{,}\) \(f(b) = c\text{,}\) \(f(c) = e\text{,}\) \(f(d) = b\text{,}\) \(f(e) = a\text{.}\)
4.1.6
Solution Three of the graphs are bipartite. The one which is not is \(C_7\) (second from the right). To see that the three graphs are bipartite, we can just give the bipartition into two sets \(A\) and \(B\text{,}\) as labeled below: The graph \(C_7\) is not bipartite because it is an odd cycle. You would want to put every other vertex into the set \(A\text{,}\) but if you travel clockwise in this fashion, the last vertex will also be put into the set \(A\text{,}\) leaving two \(A\) vertices adjacent (which makes it not a bipartition).
4.1.8
Solution For example: This is not possible if we require the graphs to be connected. If not, we could take \(C_8\) as one graph and two copies of \(C_4\) as the other. Not possible. If you have a graph with 5 vertices all of degree 4, then every vertex must be adjacent to every other vertex. This is the graph \(K_5\text{.}\) This is not possible. In fact, there is not even one graph with this property (such a graph would have \(5\cdot 3/2 = 7.5\) edges).
Solutions for Section 4.2
4.2.1
Solution No. A (connected) planar graph must satisfy Euler's formula: \(v - e + f = 2\text{.}\) Here \(v - e + f = 6 - 10 + 5 = 1\text{.}\)
4.2.2
Solution \(G\) has 10 edges, since \(10 = \frac{2+2+3+4+4+5}{2}\text{.}\) It could be planar, and then it would have 6 faces, using Euler's formula: \(6-10+f = 2\) means \(f = 6\text{.}\) To make sure that it is actually planar though, we would need to draw a graph with those vertex degrees without edges crossing. This can be done by trial and error (and is possible).
4.2.3
Solution Say the last polyhedron has \(n\) edges, and also \(n\) vertices. The total number of edges the polyhedron has then is \((7 \cdot 3 + 4 \cdot 4 + n)/2 = (37 + n)/2\text{.}\) In particular, we know the last face must have an odd number of edges. We also have that \(v = 11 \text{.}\) By Euler's formula, we have \(11 - (37+n)/2 + 12 = 2\text{,}\) and solving for \(n\) we get \(n = 5\text{,}\) so the last face is a pentagon.
4.2.5
Solution Let \(P(n)\) be the statement, "every planar graph containing \(n\) edges satisfies \(v - n + f = 2\text{.}\)" We will show \(P(n)\) is true for all \(n \ge 0\text{.}\) Base case: there is only one graph with zero edges, namely a single isolated vertex. In this case \(v = 1\text{,}\) \(f = 1\) and \(e = 0\text{,}\) so Euler's formula holds. Inductive case: Suppose \(P(k)\) is true for some arbitrary \(k \ge 0\text{.}\) Now consider an arbitrary graph containing \(k+1\) edges (and \(v\) vertices and \(f\) faces). No matter what this graph looks like, we can remove a single edge to get a graph with \(k\) edges which we can apply the inductive hypothesis to. There are two possibilities. First, the edge we remove might be incident to a degree 1 vertex. In this case, also remove that vertex. The smaller graph will now satisfy \(v-1 - k + f = 2\) by the induction hypothesis (removing the edge and vertex did not reduce the number of faces). Adding the edge and vertex back gives \(v - (k+1) + f = 2\text{,}\) as required. The second case is that the edge we remove is incident to vertices of degree greater than one. In this case, removing the edge will keep the number of vertices the same but reduce the number of faces by one. So by the inductive hypothesis we will have \(v - k + f-1 = 2\text{.}\) Adding the edge back will give \(v - (k+1) + f = 2\) as needed. Therefore, by the principle of mathematical induction, Euler's formula holds for all planar graphs. Proof
4.2.9
Solution We know in any planar graph the number of faces \(f\) satisfies \(3f \le 2e\) since each face is bounded by at least three edges, but each edge borders two faces. Combine this with Euler's formula: Proof
Solutions for Section 4.3
4.3.1
Solution 2, since the graph is bipartite. One color for the top set of vertices, another color for the bottom set of vertices.
4.3.2
Solution For example, \(K_6\text{.}\) If the chromatic number is 6, then the graph is not planar; the 4-color theorem states that all planar graphs can be colored with 4 or fewer colors.
4.3.3
Solution The chromatic numbers are 2, 3, 4, 5, and 3 respectively from left to right.
4.3.5
Solution The cube can be represented as a planar graph and colored with two colors as follows: Since it would be impossible to color the vertices with a single color, we see that the cube has chromatic number 2 (it is bipartite).
4.3.8
Solution The wheel graph below has this property. The outside of the wheel forms an odd cycle, so requires 3 colors, the center of the wheel must be different than all the outside vertices. 
4.3.10
Solution If we drew a graph with each letter representing a vertex, and each edge connecting two letters that were consecutive in the alphabet, we would have a graph containing two vertices of degree 1 (A and Z) and the remaining 24 vertices all of degree 2 (for example, \(D\) would be adjacent to both \(C\) and \(E\)). By Brooks' theorem, this graph has chromatic number at most 2, as that is the maximal degree in the graph and the graph is not a complete graph or odd cycle. Thus only two boxes are needed.
Solutions for Section 4.4
4.4.1
Solution This is a question about finding Euler paths. Draw a graph with a vertex in each state, and connect vertices if their states share a border. Exactly two vertices will have odd degree: the vertices for Nevada and Utah. Thus you must start your road trip at in one of those states and end it in the other.
4.4.2
Solution
4.4.4
Solution When \(n\) is odd, \(K_n\) contains an Euler circuit. This is because every vertex has degree \(n-1\text{,}\) so an odd \(n\) results in all degrees being even.
4.4.5
Solution If both \(m\) and \(n\) are even, then \(K_{m,n}\) has an Euler circuit. When both are odd, there is no Euler path or circuit. If one is 2 and the other is odd, then there is an Euler path but not an Euler circuit.
4.4.6
Solution All values of \(n\text{.}\) In particular, \(K_n\) contains \(C_n\) as a subgroup, which is a cycle that includes every vertex.
4.4.7
Solution As long as \(|m-n| \le 1\text{,}\) the graph \(K_{m,n}\) will have a Hamilton path. To have a Hamilton cycle, we must have \(m=n\text{.}\)
4.4.8
Solution If we build one bridge, we can have an Euler path. Two bridges must be built for an Euler circuit. 
4.4.9
Solution We are looking for a Hamiltonian cycle, and this graph does have one: 
Solutions for Section 4.5
4.5.1
Solution The first and third graphs have a matching, shown in bold (there are other matchings as well). The middle graph does not have a matching. If you look at the three circled vertices, you see that they only have two neighbors, which violates the matching condition \(\card{N(S)} \ge \card{S}\) (the three circled vertices form the set \(S\)).
Solutions for Section 4.6
4.6.1
Solution The first and the third graphs are the same (try dragging vertices around to make the pictures match up), but the middle graph is different (which you can see, for example, by noting that the middle graph has only one vertex of degree 2, while the others have two such vertices).
4.6.2
Solution The first (and third) graphs contain an Euler path. All the graphs are planar.
4.6.3
Solution For example, \(K_5\text{.}\)
4.6.4
Solution For example, \(K_{3,3}\text{.}\)
4.6.5
Solution Yes. According to Euler's formula it would have 2 faces. It does. The only such graph is \(C_{10}\text{.}\)
4.6.6
Solution Only if \(n \ge 6\) and is even. None. 12. Such a graph would have \(\frac{5n}{2}\) edges. If the graph is planar, then \(n - \frac{5n}{2} + f = 2\) so there would be \(\frac{4+3n}{2}\) faces. Also, we must have \(3f \le 2e\text{,}\) since the graph is simple. So we must have \(3\left(\frac{4 + 3n}{2}\right) \le 5n\text{.}\) Solving for \(n\) gives \(n \ge 12\text{.}\)
4.6.7
Solution There were 24 couples: 6 choices for the girl and 4 choices for the boy. There were 45 couples: \({10 \choose 2}\) since we must choose two of the 10 people to dance together. For part (a), we are counting the number of edges in \(K_{4,6}\text{.}\) In part (b) we count the edges of \(K_{10}\text{.}\)
4.6.8
Solution Yes, as long as \(n\) is even. If \(n\) were odd, then corresponding graph would have an odd number of odd degree vertices, which is impossible.
4.6.9
Solution No. The 9 triangles each contribute 3 edges, and the 6 pentagons contribute 5 edges. This gives a total of 57, which is exactly twice the number of edges, since each edge borders exactly 2 faces. But 57 is odd, so this is impossible. Now adding up all the edges of all the 16 polygons gives a total of 64, meaning there would be 32 edges in the polyhedron. We can then use Euler's formula \(v - e + f = 2\) to deduce that there must be 18 vertices. If you add up all the vertices from each polygon separately, we get a total of 64. This is not divisible by 3, so it cannot be that each vertex belongs to exactly 3 faces. Could they all belong to 4 faces? That would mean there were \(64/4 = 16\) vertices, but we know from Euler's formula that there must be 18 vertices. We can write \(64 = 3x + 4y\) and solve for \(x\) and \(y\) (as integers). We get that there must be 10 vertices with degree 4 and 8 with degree 3. (Note the number of faces joined at a vertex is equal to its degree in graph theoretic terms.)
4.6.10
Solution No. Every polyhedron can be represented as a planar graph, and the Four Color Theorem says that every planar graph has chromatic number at most 4.
4.6.11
Solution \(K_{n,n}\) has \(n^2\) edges. The graph will have an Euler circuit when \(n\) is even. The graph will be planar only when \(n \lt 3\text{.}\)
4.6.12
Solution \(G\) has 8 edges (since the sum of the degrees is 16). If \(G\) is planar, then it will have 4 faces (since \(6 - 8 + 4 = 2\)). \(G\) does not have an Euler path since there are more than 2 vertices of odd degree.
4.6.13
Solution \(7\) colors. Thus \(K_7\) is not planar (by the contrapositive of the Four Color Theorem).
4.6.14
Solution The chromatic number of \(K_{3,4}\) is 2, since the graph is bipartite. You cannot say whether the graph is planar based on this coloring (the converse of the Four Color Theorem is not true). In fact, the graph is not planar, since it contains \(K_{3,3}\) as a subgraph.
4.6.15
Solution For all these questions, we are really coloring the vertices of a graph. You get the graph by first drawing a planar representation of the polyhedron and then taking its planar dual: put a vertex in the center of each face (including the outside) and connect two vertices if their faces share an edge. Since the planar dual of a dodecahedron contains a 5-wheel, it's chromatic number is at least 4. Alternatively, suppose you could color the faces using 3 colors without any two adjacent faces colored the same. Take any face and color it blue. The 5 pentagons bordering this blue pentagon cannot be colored blue. Color the first one red. Its two neighbors (adjacent to the blue pentagon) get colored green. The remaining 2 cannot be blue or green, but also cannot both be red since they are adjacent to each other. Thus a 4th color is needed. The planar dual of the dodecahedron is itself a planar graph. Thus by the 4-color theorem, it can be colored using only 4 colors without two adjacent vertices (corresponding to the faces of the polyhedron) being colored identically. The cube can be properly 3-colored. Color the "top" and "bottom" red, the "front" and "back" blue, and the "left" and "right" green.
4.6.16
Solution \(G\) has \(13\) edges, since we need \(7 - e + 8 = 2\text{.}\)
4.6.17
Solution The graph does have an Euler path, but not an Euler circuit. There are exactly two vertices with odd degree. The path starts at one and ends at the other. The graph is planar. Even though as it is drawn edges cross, it is easy to redraw it without edges crossing. The graph is not bipartite (there is an odd cycle), nor complete. The chromatic number of the graph is 3.
4.6.18
Solution False. For example, \(K_{3,3}\) is not planar. True. The graph is bipartite so it is possible to divide the vertices into two groups with no edges between vertices in the same group. Thus we can color all the vertices of one group red and the other group blue. False. \(K_{3,3}\) has 6 vertices with degree 3, so contains no Euler path. False. \(K_{3,3}\) again. False. The sum of the degrees of all vertices is even for all graphs so this property does not imply that the graph is bipartite.
4.6.19
Solution If a graph has an Euler path, then it is planar. If a graph does not have an Euler path, then it is not planar. There is a graph which is planar and does not have an Euler path. Yes. In fact, in this case it is because the original statement is false. False. \(K_4\) is planar but does not have an Euler path. False. \(K_5\) has an Euler path but is not planar.
Solutions for Section 5.1
5.1.1
Solution
5.1.2
Solution
5.1.3
Solution The second derivative of \(\dfrac{1}{1-x}\) is \(\dfrac{2}{(1-x)^3}\) which expands to \(2 + 6x + 12x^2 + 20x^3 + 30x^4 + \cdots\text{.}\) Dividing by 2 gives the generating function for the triangular numbers. Compute \(A - xA\) and you get \(1 + 2x + 3x^2 + 4x^3 + \cdots\) which can be written as \(\dfrac{1}{(1-x)^2}\text{.}\) Solving for \(A\) gives the correct generating function. The triangular numbers are the sum of the first \(n\) numbers \(1,2,3,4, \ldots\text{.}\) To get the sequence of partial sums, we multiply by \(\frac{1}{1-x}\text{.}\) So this gives the correct generating function again.
5.1.4
Solution Call the generating function \(A\text{.}\) Compute \(A - xA = 4 + x + 2x^2 + 3x^3 + 4x^4 + \cdots\text{.}\) Thus \(A - xA = 4 + \dfrac{x}{(1-x)^2}\text{.}\) Solving for \(A\) gives \(\d\frac{4}{1-x} + \frac{x}{(1-x)^3}\text{.}\)
5.1.5
Solution \(\dfrac{1+2x}{1-3x + x^2}\text{.}\)
5.1.6
Solution Compute \(A - xA - x^2A\) and the solve for \(A\text{.}\) The generating function will be \(\dfrac{x}{1-x-x^2}\text{.}\)
5.1.7
Solution \(\dfrac{x}{(1-x)(1-x-x^2)}\text{.}\)
5.1.8
Solution \(\dfrac{2}{1-5x} + \dfrac{7}{1+3x}\text{.}\)
5.1.9
Solution \(a_n = 3\cdot 4^{n-1} + 1\text{.}\)
5.1.10
Solution Hint: you should "multiply" the two sequences. Answer: 158.
5.1.11
Solution Starting with \(\frac{1}{1-x} = 1 + x + x^2 + x^3 +\cdots\text{,}\) we can take derivatives of both sides, given \(\frac{1}{(1-x)^2} = 1 + 2x + 3x^2 + \cdots\text{.}\) By the definition of generating functions, this says that \(\frac{1}{(1-x)^2}\) generates the sequence 1, 2, 3…. You can also find this using differencing or by multiplying.
5.1.12
Solution
5.1.13
Solution
5.1.14
Solution \(\frac{1}{1+2x}\text{.}\)
5.1.15
Solution \(\frac{x^3}{(1-x)^2} + \frac{1}{1-x}\text{.}\)
5.1.16
Solution We know \(2 + 4x + 6x^3 + \cdots = \frac{2}{(1-x)^2}\text{.}\)
Solutions for Section 5.2
5.2.1
Solution Suppose \(a \mid b\text{.}\) Then \(b\) is a multiple of \(a\text{,}\) or in other words, \(b = ak\) for some \(k\text{.}\) But then \(bc = akc\text{,}\) and since \(kc\) is an integer, this says \(bc\) is a multiple of \(a\text{.}\) In other words, \(a \mid bc\text{.}\) Proof
5.2.2
Solution Assume \(a \mid b\) and \(a \mid c\text{.}\) This means that \(b\) and \(c\) are both multiples of \(a\text{,}\) so \(b = am\) and \(c = an\) for integers \(m\) and \(n\text{.}\) Then \(b+c = am+an = a(m+n)\text{,}\) so \(b+c\) is a multiple of \(a\text{,}\) or equivalently, \(a \mid b+c\text{.}\) Similarly, \(b-c = am-an = a(m-n)\text{,}\) so \(b-c\) is a multiple of \(a\text{,}\) which is to say \(a \mid b-c\text{.}\) Proof
5.2.3
Solution \(\{\ldots, -8, -4, 0, 4, 8, 12, \ldots\}\text{,}\) \(\{\ldots, -7, -3, 1, 5, 9, 13, \ldots\}\text{,}\) \(\{\ldots, -6, -2, 2, 6, 10, 14, \ldots\}\text{,}\) and \(\{\ldots, -5, -1, 3, 7, 11, 15, \ldots\}\text{.}\)
5.2.4
Solution Assume \(a \equiv b \pmod n\) and \(c \equiv d \pmod n\text{.}\) This means \(a = b + kn\) and \(c = d + jn\) for some integers \(k\) and \(j\text{.}\) Consider \(a-c\text{.}\) We have: In other words, \(a-c\) is \(b-d\) more than some multiple of \(n\text{,}\) so \(a-c \equiv b-d \pmod n\text{.}\) Proof
5.2.5
Solution
5.2.6
Solution For all of these, just plug in all integers between 0 and the modulus to see which, if any, work. No solutions. No solutions. No solutions.
5.2.7
Solution First reduce each number modulo 9, which can be done by adding up the digits of the numbers. Answer: \(x = 2 + 9k\) for \(k \in \Z\text{.}\)
5.2.8
Solution We must solve \(7x + 5 \equiv 2 \pmod{11}\text{.}\) This gives \(x \equiv 9 \pmod{11}\text{.}\) In general, \(x = 9 + 11k\text{,}\) but when you divide any such \(x\) by 11, the remainder will be 9.
5.2.9
Solution Divide through by 2: \(3x + 5y = 16\text{.}\) Convert to a congruence, modulo 3: \(5y \equiv 16 \pmod 3\text{,}\) which reduces to \(2y \equiv 1 \pmod 3\text{.}\) So \(y \equiv 2 \pmod 3\) or \(y = 2 + 3k\text{.}\) Plug this back into \(3x + 5y = 16\) and solve for \(x\text{,}\) to get \(x = 2-5k\text{.}\) So the general solution is \(x = 2-5k\) and \(y = 2+3k\) for \(k \in \Z\text{.}\)
5.2.10
Solution First, solve the Diophantine equation \(13x + 20 y = 2\text{.}\) The general solution is \(x = -6 - 20k\) and \(y = 4+13k\text{.}\) Now if \(k = 0\text{,}\) this correspond to filling the 20 oz. bottle 4 times, and emptying the 13 oz. bottle 6 times, which would require 80 oz. of water. Increasing \(k\) would require considerably more water. Perhaps \(k = -1\) would be better? Then we would have \(x = -6+20 = 14\) and \(y = 4-13 = -11\text{,}\) which describes the solution where we fill the 13 oz. bottle 14 times, and empty the 20 oz. bottle 11 times. This would require 182 oz. of water. Thus the most efficient procedure is to repeatedly fill the 20 oz bottle, emptying it into the 13 oz bottle, and discarding full 13 oz. bottles, which requires 80 oz. of water.
Discrete Mathematics Levin 0.2 11 Answers
Source: http://discrete.openmathbooks.org/dmoi2/appendix-1.html
Posted by: wardsleve2000.blogspot.com
0 Response to "Discrete Mathematics Levin 0.2 11 Answers"
Post a Comment