6.042/18.] Mathematics for Computer Science March 15, 2005 Srini devadas and Eric Lehman Problem set 6 Solutions Due: Monday, March 28 at 9 PM Problem 1. Sammy the Shark is a financial service provider who offers loans on the fol- lowing terms Sammy loans a client m dollars in the morning. This puts the client m dollars in debt to sammy. Each evening, Sammy first charges a"service fee", which increases the clients debt y f dollars, and then Sammy charges interest, which multiplies the debt by a factor of p. For example, if Sammys interest rate were a modest 5% per day, then p would be1.05 (a)What is the client's debt at the end of the first day Solution. At the end of the first day, the client owes Sammy(m f)p=mp+ fp doll ars (b) What is the clients debt at the end of the second day? Solution((m+ f)p+ fp= mp2+ fp2+ fp (c) Write a formula for the client's debt after d days and find an equivalent clos orm Solution. The clients debt after three days is (((m+ f)p+ fp+f)p=mp'+fp+fp+ fp generalizing from this pattern the client owes k=1 dollars after d days. Applying the formula for a geometric sum gives mp+/./pd+ Problem 2. Find closed-form expressions equal to the following sums. Show your work
� � � 6.042/18.062J Mathematics for Computer Science March 15, 2005 Srini Devadas and Eric Lehman Problem Set 6 Solutions Due: Monday, March 28 at 9 PM Problem 1. Sammy the Shark is a financial service provider who offers loans on the following terms. • Sammy loans a client m dollars in the morning. This puts the client m dollars in debt to Sammy. • Each evening, Sammy first charges a “service fee”, which increases the client’s debt by f dollars, and then Sammy charges interest, which multiplies the debt by a factor of p. For example, if Sammy’s interest rate were a modest 5% per day, then p would be 1.05. (a) What is the client’s debt at the end of the first day? Solution. At the end of the first day, the client owes Sammy (m + f)p = mp + fp dollars. (b) What is the client’s debt at the end of the second day? Solution. ((m + f)p + f)p = mp2 + fp2 + fp (c) Write a formula for the client’s debt after d days and find an equivalent closed form. Solution. The client’s debt after three days is (((m + f)p + f)p + f)p = mp 3 + fp 3 + fp 2 + fp. Generalizing from this pattern, the client owes d mp d + fp k k=1 dollars after d days. Applying the formula for a geometric sum gives: d+1 p − 1 − 1 mp d + f · p − 1 Problem 2. Find closedform expressions equal to the following sums. Show your work
92-72 Solution. Split the expression into two geometric series and then apply the formula for the sum of a geometric series 92-72 11/9 11/7 Solution. Taking the logarithm reduces this product to an easy sum 4+5=3g3(I=34+5) 4i+5 2n(n+1)+5n 5/3 j=1i=0 2j1/3 Solution. This fearsome-looking sum is a paper tiger; we just apply the formula for the sum of a geometric series followed by the formula for the sum of an arithmeti series. n(n+)(n+1)
� � � 2 Problem Set 6 (a) �n 9i − 7i 11i i=0 Solution. Split the expression into two geometric series and then apply the formula for the sum of a geometric series. �n n � �i n � 9i − 7i � 9 � 7 �i = 11i 11 − 11 i=0 i=0 i=0 � 9 �n+1 � 7 �n+1 1 − 11 1 − 11 = 9 1 − 11 − � �n+1 7 1 − 11 � �n+1 11 9 11 7 11 = − + + 2 · 11 4 · 11 4 (b) n 34i+5 i=1 Solution. Taking the logarithm reduces this product to an easy sum. n 3log3( Qn 34i+5) 34i+5 = i=1 i=1 Pn = 3 4i+5 i=1 = 32n(n+1)+5n (c) ��n ∞ � 1 �i j5/3 · 1 − 2j1/3 j=1 i=0 Solution. This fearsomelooking sum is a paper tiger; we just apply the formula for the sum of a geometric series followed by the formula for the sum of an arithmetic series. �� � n 1 n ∞ �i � 1 j5/3 · 1 − 2j1/3 = j5/3 · � 1 � j=1 i=0 j=1 1 − 1 − 2j1/3 n = 2j2 j=1 1 2n(n + 2 )(n + 1) = 3
Problem set 6 Problem 3. There is a bug on the edge of a 1-meter rug. The bug wants to cross to the other side of the rug. It crawls at 1 cm per second. However, at the end of each second,a malicious first-grader named Mildred Anderson stretches the rug by 1 meter. Assume that her action is instantaneous and the rug stretches uniformly. Thus, heres what happens in the first few seconds The bug walks 1 cm in the first second, so 99 cm remain ahead Mildred stretches the rug by 1 meter, which doubles its length. So now there are 2 cm behind the bug and 198 cm ahead The bug walks another 1 cm in the next second, leaving 3 cm behind and 197 cm Then Mildred strikes, stretching the rug from 2 meters to 3 meters. So there are now 33/2)=4.5 cm behind the bug and 197( 3/2)=295. 5 cm ahead The bug walks another 1 cm in the third second, and so on Your job is to determine this poor bugs fate (a) During second i, what fraction of the rug does the bug cross? Solution. During second i, the length of the rug is 100i cm and the bug crosses 1 cm. Therefore, the fraction that the bug crosses is 1/100i (b)Over the first n seconds, what fraction of the rug does the bug cross altogether? Solution. The bug crosses 1/100 of the rug in the first second, 1/200 in the second, 300 in the third, and so forth. Thus, over the first n seconds, the fraction crossed by the bug is This formula is valid only until the bug reaches the far side of the rug (c) Approximately how many seconds does the bug need to cross the entire rug Solution. The bug arrives at the far side when the fraction it has crossed reaches 1. This occurs when n, the number of seconds elapsed, is sufficiently large that Hn/100 1 Now Hn is approximately Inn, so the bug arrives about when ln >1 Inn >100
Problem Set 6 3 Problem 3. There is a bug on the edge of a 1meter rug. The bug wants to cross to the other side of the rug. It crawls at 1 cm per second. However, at the end of each second, a malicious firstgrader named Mildred Anderson stretches the rug by 1 meter. Assume that her action is instantaneous and the rug stretches uniformly. Thus, here’s what happens in the first few seconds: • The bug walks 1 cm in the first second, so 99 cm remain ahead. • Mildred stretches the rug by 1 meter, which doubles its length. So now there are 2 cm behind the bug and 198 cm ahead. • The bug walks another 1 cm in the next second, leaving 3 cm behind and 197 cm ahead. • Then Mildred strikes, stretching the rug from 2 meters to 3 meters. So there are now 3 · (3/2) = 4.5 cm behind the bug and 197 · (3/2) = 295.5 cm ahead. • The bug walks another 1 cm in the third second, and so on. Your job is to determine this poor bug’s fate. (a) During second i, what fraction of the rug does the bug cross? Solution. During second i, the length of the rug is 100i cm and the bug crosses 1 cm. Therefore, the fraction that the bug crosses is 1/100i. (b) Over the first n seconds, what fraction of the rug does the bug cross altogether? Solution. The bug crosses 1/100 of the rug in the first second, 1/200 in the second, 1/300 in the third, and so forth. Thus, over the first n seconds, the fraction crossed by the bug is: �n 1 = Hn/100 100k k=1 (This formula is valid only until the bug reaches the far side of the rug.) (c) Approximately how many seconds does the bug need to cross the entire rug? Solution. The bug arrives at the far side when the fraction it has crossed reaches 1. This occurs when n, the number of seconds elapsed, is sufficiently large that Hn/100 ≥ 1. Now Hn is approximately ln n, so the bug arrives about when: ln n 100 ≥ 1 ln n ≥ 100 100 n ≥ e ≈ 1043 seconds
Problem set 6 that differ by at most 0. 1. Show your work t Problem 4. Use integration to find lower and upper bounds on the following infinite sum 1111 To achieve this accuracy, add up the first few terms explicitly and then use integration to bound all remaining terms Solution. The sum of the first three terms is: 11149 An upper bound on the remaining terms is And a lower bound is x+1)2 Overall, we have 58491 49161 36-36 +-<S<+ These bounds differ by 1/12<0.1. The actual value of the sum is 2/6, though the proof is not easy. Problem 5. A seasoned MIT undergraduate can Complete a problem set in 2 days Write a paper in 2 days Take a 2-day road trip Study for an exam in 1 day. Play foosball for an entire day. An n-day schedule is a sequence of activities that require a total of n days fe here are three possible 7-day schedules 中 pset, foosball Paper, foosball, pset, study road t ad trip, road trip, stud
� 4 Problem Set 6 Problem 4. Use integration to find lower and upper bounds on the following infinite sum that differ by at most 0.1. Show your work. 1 1 1 1 S = + + + + . . . 12 22 32 42 To achieve this accuracy, add up the first few terms explicitly and then use integration to bound all remaining terms. Solution. The sum of the first three terms is: 1 1 1 49 s = + + = 12 22 32 36 An upper bound on the remaining terms is: ∞ 1 1 dx = 3 x2 3 And a lower bound is: � ∞ 1 1 dx = (x + 1)2 3 4 Overall, we have: 58 49 1 49 1 61 + = 36 ≤ 36 + 4 ≤ S ≤ 36 3 36 These bounds differ by 1/12 < 0.1. The actual value of the sum is π2/6, though the proof is not easy. Problem 5. A seasoned MIT undergraduate can: • Complete a problem set in 2 days. • Write a paper in 2 days. • Take a 2day road trip. • Study for an exam in 1 day. • Play foosball for an entire day. An nday schedule is a sequence of activities that require a total of n days. For example, here are three possible 7day schedules: pset, paper, pset, foosball paper, study, foosball, pset, study road trip, road trip, road trip, study
Problem set 6 5 (a) Express the number of possible n-day schedules using a recurrence equation and sufficient base cases Solution S(0)=1, S(1)=2 any schedule for n> 1 days ends with one of 3 possible 2-day activities or one of 2 possible 1-day activities. So S(m)=2S(m-1)+3S(n-2 for n >1 (b) Find a closed-form expression for the number of possible n-day schedules br Solution. The characteristic polynomial for this linear homogeneous recurrence is 2-2.c-3=(r+1(a-3). Hence the solution is of the form S(n)=a(-1)"+b3n Letting n=0, we conclude that a+b= l, and letting n= l, we conclude -a+3b= 2, so b=3/4, a=1/4, and the solution is (-1) 4 Problem 6. Find a closed-form expression for T(n), which is defined by the following recurrence T(0)=0 T(1)=1 T(n)=5T(n-1)-6T(n-2)+6 for all n 22 Solution. The characteristic equation is x2-5x+6=0, which has roots r=2 and 3. Thus, the homogenous solution is T(m)=A.2n+B·3 For a particular solution, let's first guess T(n)=c Our guess was correct; T(n)=3 is a particular solution. Adding this to the homogenous solution gives the general solution T(m)=A.2+B.32+3
Problem Set 6 5 (a) Express the number of possible nday schedules using a recurrence equation and sufficient base cases. Solution. S(0) = 1, S(1) = 2. Any schedule for n > 1 days ends with one of 3 possible 2day activities or one of 2 possible 1day activities. So S(n) = 2S(n − 1) + 3S(n − 2) for n > 1. (b) Find a closedform expression for the number of possible nday schedules by solving the recurrence. Solution. The characteristic polynomial for this linear homogeneous recurrence is 2 x − 2x − 3 = (x + 1)(x − 3). Hence the solution is of the form S(n) = a(−1)n + b3n . Letting n = 0, we conclude that a+b = 1, and letting n = 1, we conclude −a+3b = 2, so b = 3/4, a = 1/4, and the solution is: 3n+1 + (−1)n S(n) = . 4 Problem 6. Find a closedform expression for T(n), which is defined by the following recurrence: T(0) = 0 T(1) = 1 T(n) = 5T(n − 1) − 6T(n − 2) + 6 for all n ≥ 2 2 Solution. The characteristic equation is x − 5x + 6 = 0, which has roots x = 2 and x = 3. Thus, the homogenous solution is: 2n 3n T(n) = A · + B · For a particular solution, let’s first guess T(n) = c: c = 5c − 6c + 6 ⇒ c = 3 Our guess was correct; T(n) = 3 is a particular solution. Adding this to the homogenous solution gives the general solution: T(n) = 2n 3n A · + B · + 3