MAT 141 Discrete Mathematics II, Section 701 AQ 2017 Assignment 4 Deadlines Assignment 4 Problem 1 (A4P1) due online through D2L at 3pm on Friday, October 6. D2L Reading Quiz due Sunday, October 8, at 6pm The other written homework problems are due in hardcopy at the start of class on October 9. ........................................................................................................ Reading Homework Read the following sections of the textbook, and then complete the reading quiz posted in the Quizzes area of our course D2L site. \u0001 - Section 5.1 (pages 237-239) and Section 9.5 (pages 565-571), review of factorials and nr - Section 5.4 (pages 268-274) - Section 4.8 (assigned last week; review as needed) - Section 5.5 (assigned last week; review as needed for the written homework) In the Content/Chapter 5 Videos folder on D2L, there are links to the following relevant videos: - 5.4 Strong Mathematical Induction - 5.6 Proving a proposition about Fibonacci numbers Additional practice exercises related to the reading. You are responsible for being able to complete all of these exercises; some of this material will be assessed through the reading quiz. (Most of these exercises have solutions in the back of the text.) - Section 5.1 # 62, 65, 66, 68, 73, 75, 81, 84 - Section 9.5 # 1, 5ab - Section 4.8 # 6, 9, 10, 13, 14 ........................................................................................................ Written Homework A4P1 is due online through D2L by 3pm on Friday, October 6. The remaining problems are due in hardcopy at the start of class on Monday, October 9. Directions for homework submitted through D2L: See the directions posted on Assignments 1 and 2. Directions for hardcopy homework assignments: See the directions posted on Assignments 1 and 2. 1 A4P1: Consider the simple algorithm below (which should look very similar to part of Algorithm 5.1.1): Inputs: n, q [nonnegative integers], r[0], r[1], . . . , r[i 1] [an array of integers, each 0 or 1] Algorithm body: 1. r[i] := q mod 2 2. q := q div 2 3. i := i + 1 Outputs: n, q [nonnegative integers] r[0], r[1], r[2], . . . , r[i] [an array of integers, each 0 or 1] Suppose the inputs to this algorithm satisfy the relationship n = q 2i + r[i 1] 2i1 + + r[1] 21 + r[0] 20 . Prove that the output values of the algorithm will satisfy the relationship n = q 2i+1 + r[i] 2i + r[i 1] 2i1 + + r[1] 21 + r[0] 20 . Hint: Review the definitions of div and mod in Section 4.5. In particular, what fundamental equation relates the values of n, d, n mod d, and n div d? A4P2: Imagine as in A2P3 that you have blocks that come in two sizes: 1 1 squares and 2 1 rectangles. But now suppose that the 1 1 squares come in two colorsblack or whiteand the 2 1 rectangles come in three colorsred, green, or blue. For each integer n 1, let cn be the number of different trains of length n that can be made using these colored blocks. (For example, c1 = 2, because there are precisely two ways to make a train of length 1 using the colored blocks: either use a single 1 1 white block, or use a single 1 1 black block.) Compute c15 , and give a complete justification for why your answer is correct. Hint: It may be helpful to find and then use a recurrence relation for the sequence c1 , c2 , c3 , . . .. However, you must give a complete justification for why your recurrence relation is true. In other words, you must give a complete justification for why your recurrence relation (always) computes correct values. It is not sufficient to simply check that the recurrence relation works for the first few values in the sequence. A4P3: Imagine there are n 2 friends standing in a row (Friend 1, Friend 2, . . . , up to Friend n). The friends decide to play the \"row reversal\" game. The goal is for the friends to completely reverse their original order (i.e., to end up in the order Friend n, Friend n 1, . . . , down to Friend 1). Only one legal move may be made at a time, and the only type of legal move is as follows: two friends who are standing next to each other may switch places. (So for example, if there are four friends playing, and if their current ordering is 1, 3, 2, 4, then Friends 2 and 4 could swap places, resulting in 1, 3, 4, 2. Alternatively, starting from 1, 3, 2, 4, Friends 1 and 3 could swap places, resulting in 3, 1, 2, 4.) Prove (by mathematical induction), that when n friends play the row reversal game, it is possible for them to finish the game in 21 n2 21 n total moves or fewer. A4P4: (Optional) You may again attempt the brick-stacking problem from Assignment 2. An \"Acceptable\" or \"Polished\" solution will earn one token. 2