Massachusetts Institute of Technology 6.042J/18.062J, Fall ’05: Mathematics for Computer Science Prof. Albert R. Meyer and Prof. Ronitt Rubinfeld October 26 revised October 25, 2005, 1134 minutes Solutions to InClass Problems Week 8, Wed. Problem 1. We begin with two large glasses. The ﬁrst glass contains a pint of water, and the second contains a pint of wine. We pour 1/3 of a pint from the ﬁrst glass into the second, stir up the wine/water mixture in the second glass, and then pour 1/3 of a pint of the mix back into the ﬁrst glass and repeat this pouring backandforth process a total of n times. (a) Describe a closed form formula for the amount of wine in the ﬁrst glass after n backandforth pourings. Solution. The state of the system of glasses/wine/water at the beginning of a round of pouring and pouring back is determined by the total amount of wine in the ﬁrst glass. Suppose at the beginning of some round, the ﬁrst glass contains w pints of wine, 0 ≤ w ≤ 1 and 1 − w pints of water. The second glass contains the rest of the wine and water. Pouring 1/3 pint from ﬁrst glass to second leaves 2/3 pints of liquid and (2/3)w wine in the ﬁrst glass, and 4/3 pints of liquid and 1 − (2/3)w wine in the second glass. Pouring 1/3 pint back from second into ﬁrst transfers a proportion of (1/3)/(4/3) of the wine in the second glass into the ﬁrst. So the round completes with both glasses containing a pint of liquid, and the ﬁrst glass containing (2/3)w + (1/4)(1 − (2/3)w) = 1/4 + w/2 pints of wine. After one more round, the ﬁrst glass contains 1/4 + (1/4 + w/2)/2 = 1/4 + 1/8 + w/22 pints of wine, and after n more rounds w/2n + Σni=1 (1/2)i+1 = w/2n + (1/2)Σni=1 (1/2)i = w/2n + (1/2)(−1 + Σni=0 (1/2)i ) = w/2n + (1/2)(−1 + (1 − (1/2)n+1 )/(1 − 1/2)) = w/2n − 1/2 + 1 − (1/2)n+1 = w/2n + 1/2 − (1/2)n+1 . Since w = 0 initially, the pints of wine in the ﬁrst glass after n rounds is 1/2 − (1/2)n+1 . � Copyright © 2005, Prof. Albert R. Meyer. 2 Solutions to InClass Problems Week 8, Wed. (b) What is the limit of the amount of wine in each glass as n approaches inﬁnity? Solution. The limiting amount of wine in the ﬁrst glass approaches 1/2 from below as n ap proaches inﬁnity. In fact, it approaches 1/2 no matter how the wine was initially distributed. This of course is what you would expect: after a thorough mixing the glasses should contain essentially the same amount of wine. � Problem 2. Suppose you were about to enter college today and a college loan ofﬁcer offered you the following deal: $25,000 at the start of each year for four years to pay for your college tuition and an option of choosing one of the following repayment plans: Plan A: Wait four years, then repay $20,000 at the start of each year for the next ten years. Plan B: Wait ﬁve years, then repay $30,000 at the start of each year for the next ﬁve years. Suppose the annual interest rate paid by banks is 7% and does not change in the future. (a) Assuming that it’s no hardship for you to meet the terms of either payback plan, which one is a better deal? (You will need a calculator.) Solution. $1 today will be worth $1.07 next year, and $1.072 the year after, etc. So set r = Then: current value of Plan A 13 � = 20000 · ry y=4 = 9 � 20000 · ry+4 y=0 = r4 · 9 � 20000 · ry y=0 = 20000r4 · 9 � ry y=0 1 − r10 1−r = $114, 66.69 = 20000r4 · 1 1.07 . Solutions to InClass Problems Week 8, Wed. 3 current value of Plan B 9 � = 30000 · ry y=5 = 4 � 30000 · ry+5 y=0 = r5 · 4 � 30000 · ry y=0 = 30000r5 · 4 � ry y=0 1 − r5 1−r = $93, 840.63 = 30000r5 · You should clearly take Plan B. You will be paying back much less in today’s dollars. � (b) What is the loan ofﬁcer’s effective proﬁt (in today’s dollars) on the loan? Solution. The value of the money you are given is: Loan = 3 � 25000 · ry y=0 = 25000 · 3 � ry y=0 1 − r4 1−r = $90, 607.90 = 25000 · Therefore, the loan ofﬁcer’s proﬁt is effectively $3, 233. (Or $24, 059 if we are not on the ball). Problem 3. Riemann’s Zeta Function ζ(k) is deﬁned to be the inﬁnite summation: 1+ � 1 1 1 + · · · = 2k 3k jk j≥1 Below is a proof that � k≥2 (ζ(k) − 1) = 1 � 4 Solutions to InClass Problems Week 8, Wed. Justify each line of the proof. (P.S. The purpose of this exercise is to highlight some of the rules for manipulating series. Don’t worry about the signiﬁcance of this identity.) � (ζ(k) − 1) = k≥2 � k≥2 = = ⎡⎛ ⎞ ⎤ � 1 ⎠ − 1⎦ ⎣⎝ jk (1) j≥1 �� 1 jk k≥2 j≥2 �� 1 (2) jk � 1 � 1 = j2 jk j≥2 k≥0 � 1 1 · = 2 j 1 − 1/j j≥2 � 1 = j(j − 1) (3) j≥2 k≥2 (4) (5) (6) j≥2 = = = lim n→∞ lim n→∞ n � j=2 n � j=2 1 j(j − 1) (7) 1 1 − j−1 j (8) lim (1 − n→∞ 1 ) n = 1 (9) (10) Solution. (1) Deﬁnition of ζ(k). � 1 � 1 (2) Because = 1 + . jk jk j≥1 j≥2 (3) Reordering; this is ok because at this point all terms are positive. � 1 � 1 � 1 1� 1 (4) Because = = = 2 . k k+2 k 2 j j j j ·j jk k≥2 k≥0 k≥0 k≥0 (5) Sum of a geometric series. (6) Algebra inside every summand. (7) Deﬁnition of inﬁnite summation. (8) Algebra inside every summand. 1 1 1 (9) The sum telescopes: 1 is added once; every one of , , . . . , is subtracted once and then 2 3 n−1 1 added once; is subtracted once. n � (10) Simple limits.