CS 70 Discrete Mathematics and Probability TheoryFall 2011 Rao HW 2Due Friday, September 9, 5:00pmYou must write up the solution set entirely on your own. You must never look at any other students’ solutions(not even a draft), nor share your own solutions (not even a draft).Please put your answer to each problem on its own sheet of paper, and paper-clip (don’t staple!) the sheetsof paper together. Label each sheet of paper with your name, your discussion section number (101–108),and “CS70–Fall 2011”. Turn in your homework and problem x into the box labeled “CS70 – Fall 2011,Problem x ” whereon the 2nd floor of Soda Hall. Failure to follow these instructions will likely cause you toreceive no credit at all.1. (35 pts.) Practice Proving PropositionsProve or disprove each of the following statements. For each proof, state which of the proof types (asdiscussed in Lecture Note 2) you used.1. For all natural numbers n, if n is even then n2+ 2011 is odd.2. For all natural numbers n, n2+ 5n + 1 is odd.3. For all real numbers a,b, if a + b ≥ 2011 then a > 1005 or b > 1005.4. For all real numbers r, if r is irrational then r/4 is irrational.5. For all natural numbers n, 10n2> n!.2. (20 pts.) Interesting Induction1. For n ∈ N with n ≥ 2, define snbysn=1 −12×1 −13× ··· ×1 −1n.Prove that sn= 1/n for every natural number n ≥ 2.2. Let an= 3n+2+ 42n+1. Prove that 13 divides anfor every n ∈ N. (Hint: What can you say aboutan+1− 3an?)3. (28 pts.) Proofs, PerhapsWhich of the proofs below is correct? If a proof is incorrect, explain clearly and concisely where the logicalerror in the proof lies. (If the proof is correct, just mark it as correct – you don’t need to give an explanation.)Simply saying that the claim (or induction hypothesis) is false is not enough!1. Claim: (∀n ∈ N)(n2≤ n).Proof: Base Case: When n = 1, the statement is 12≤ 1 which is true.CS 70, Fall 2011, HW 2 1Induction hypothesis: Assume that k2≤ k.Inductive step: We need to show that(k + 1)2≤ k + 1Working backwards we see that:k2≤ (k + 1)2− 1 ≤ (k + 1) − 1 = k .So we get back to our original hypothesis which is assumed to be true.Hence, for every n ∈ N we know that n2≤ n. ♠2. Claim: (∀n ∈ N)(7n= 1).Proof: (uses strong induction)Base Case: Certainly 70= 1.Induction hypothesis: Assume that 7j= 1 for all 0 ≤ j ≤ k.Inductive step: We need to prove that 7k+1= 1. But,7k+1=(7k· 7k)7k−1=(1 · 1)1= 1Hence, by the Principle of Strong Induction, 7m= 1 for all m ∈ N. ♥3. Claim: For all natural numbers n ≥ 4, 2n< n!.Proof: Base case: 24= 16 and 4! = 24, so the statement is true for n = 4.Inductive step: Assume that 2n< n! for some n ∈ N. Then 2n+1= 2(2n) < 2(n!) ≤ (n + 1)(n!) =(n + 1)!, so 2n+1< (n + 1)!. By the principle of mathematical induction, the statement is true for alln ≥ 4. ♣4. Claim: All natural numbers are equal.Proof: It is sufficient to show that for any two natural numbers a and b, a = b. Further, it is sufficientto show that for all n ≥ 0, if a and b satisfy max{a, b} = n then a = b. We proceed by induction on n.Base case: If n = 0 then a and b, being natural numbers, must both be 0. So clearly a = b.Inductive step: Assume that the claim is true for some value n. Take a and b with max{a,b} =n + 1. Then max{(a − 1), (b − 1)} = n, and hence by the induction hypothesis (a − 1) = (b − 1).Consequently, a = b. ♦4. (10 pts.) Take the TokensTamara and Thuc are playing a game. They take turns removing tokens from a pile. Tamara moves first,and takes one, two or three tokens. If there are any tokens left, then it’s Thuc’s turn to take one, two or threetokens. They continue in the same way, and whoever takes the last token loses.For example, if the pile starts with three tokens, than Tamara wins by taking two tokens in her first turn,forcing Thuc to take the last token. If the pile starts with five tokens, then no matter whether Tamara startsby taking one, two or three tokens, Thuc can win by taking all the rest of the tokens except one.Prove that for all natural numbers k, if the pile starts with 4k + 1 tokens, then Thuc has a winning strategy.5. (10 pts.) Rigorous Recursion Consider the following computer program:CS 70, Fall 2011, HW 2 2REDGREENGREENREDGREENBLUEREDREDGREENGREENREDGREENBLUEREDFigure 1: An island map that has been colored using three colors, and the corresponding graph.function G(n)if n = 0 then return 0if n = 1 then return 1else return 5G(n − 1) − 6G(n − 2)Prove (using strong induction) that for all inputs n ∈ N, the value returned by the program is G(n) = 3n−2n.6. (17 pts.) Coloring CountriesExplorers have just discovered several new islands in the Pacific ocean! Each island is divided into severalcountries. As chief map-maker, your job is to make a map of each island, giving a color to each country sothat no two neighboring countries have the same color. For example, the left side of Figure 1 shows a mapthat has been colored using three colors.Unfortunately, you haven’t been to the mapmaking store in a while, and so you only have six colors to workwith: red, green, blue, purple, orange and almond toast. Fortunately, that’s enough to color any map, as weshall see!The right side of Figure 1 shows another way of looking at a map: make a vertex for each country, and drawan edge between two nodes if the countries are neighbors. The graph you get will be planar, meaning it canbe laid out so that none of the edges cross each other.1. (2 pts.) In order to color the map in Figure 1 so that no neighbors have the same color, you need atleast three different colors. (To see why, try to color it using only red and green and see what happens.)Draw a map that needs at least four different colors, and then draw the corresponding planar graph.2. (15 pts.) In order to see that six colors will be enough to color any map, prove the following theorem:Theorem: Every planar graph can be colored with six colors, in such a way that no two neighboringvertices have the same color.You may find the following lemma useful:Lemma: Every planar graph (with at least one node) has a node with at most five neighbors. (We saythe node has degree at most five.)You don’t need to prove the lemma, but you may assume it is true when proving the theorem.(In fact, it only ever takes four colors to color a planar graph – but that’s much harder to prove. Searchfor four color theorem.)CS 70, Fall 2011, HW 2
View Full Document
Unlocking...