From jacob_otto@hotmail.com Thu Jul 12 21:10:08 2001 Date: Fri, 13 Jul 2001 01:01:57 From: Jacob Otto To: dimitrik@MIT.EDU Subject: discrete math, PS-7 Discrete Math Problem Set 7 1a) 101 99 99 2 101 = 1*99+2 --> 2 = 101 - 1*99 2 1 99 = 49*2+1 ---> 1 = 99 - 49*2 gcd(99,101) = 1 = 99 - 49*2 = 99 - 49 *(101-1*99) = 99 - 49*101 + 49 *99 = 50*99-49*101 which is also equivalent to 50*101-51*99 (x=50, y=49, u=50, v=51) 1b) 35 10 10 5 35 = 3*10+5 --> 5 = 35 - 3*10 5 0 gcd(10,35) = 5 = 1*35-3*10 which is also equivalent to 32*10-9*35 (u=1, w=3, x=32, y=9) 1c) 12 7 7 5 12=1*7+5 --> 5 = 12 - 1*7 5 2 7=1*5+2 --> 2 =7-1*5 2 1 5=2*2+1 --> 1 = 5 -2*2 gcd(7,12) = 1=5 - 2*2 = 5 - 2*(7-1*5) = 3*5 -2*7 = 3*(12-1*7)-2*7=3*12-5*7 which is also equivalent to 7*7-4*12 (u=3,v=5,x=7,y=4) 1d) 42 36 36 6 42=1*36+6 --> 42-1*36 6 0 gcd(36,42) = 6 = 42-1*36 which is also equivalent to 41*36-35*42 (u=1,v=1,x=41,y=35) 2) See printout 3a) (1+x+x^2+x^3+x^4)^3 = (1 + 3x + 6x^2 + 10x^3 + 15x^4 + ...) since the coefficients are those of the 3rd diagonal of Pascal's triangle: 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 1 6 15 20 15 6 1 x^4 has coefficient 15. 3b) (1+x^2+x^4)^2 * (1+x+x^2)^2 = (1+2x^2+3x^4+2x^6+x^8) * (1 + 2x + 3x^2 + 2x^3 + x^4) Coefficient of x^4: 1+2*3+3 = 10 3c) >From a): (1+x+x^2+x^3+x^4+...) = (1+3x+6x^2+10x^3+15x^4+...) x^4 has coefficient 15 4) We have to find the number of solutions to: e(h) + e(e) + e(l) + e(p) = 5 where e(l) <=1, e(p) <=1, e(h) <=5, e(e) <=5 The generating function is: (1+x)(1+x)(1+x+x^2+x^3+x^4+x^5)(1+x+x^2+x^3+x^4+x^5) and the answer is the coefficient in fornt of x^5 which is 20. 5) 1/(1-10x+21x^2) = 1/((1-7x)(1-3x)) = A/(1-7x) + B/(1-3x) Solving for A and B: A - 3Ax + B - 7Bx = 1 implies A+B = 1 and 3A=-7B implies A=7/4 and B= -3/4 Therefore: A/(1-7x) + B/(1-3x) = (7/4)/(1-7x) - (3/4)/(1-3x) Coefficient of x^n = (7/4) * 7^n - (3/4) * 3^n = 7^(n+1)/4 - 3^(n+1)/4 6a) The distinct divisors for p^a are p^0(=1), p, p^2, p^3, ..., p^a. Therfore, number of divisors = a+1. 6b) m = p1^a1*p2^a2*...pn^an where p1, p2, ... are distinct primes. Then we have a1 + 1 choices for p1, a2 + 1 choices for p2, .... Therefore, number of distinct divisors = (a1 + 1)(a2 + 1)...(an + 1). 7) Is the coefficient of x^k in the following expression: (1+x+x^2+x^3+...)(1+x^5+x^10+x^15+...)(1+x^10+x^20+x^30+...)(1+x^25+x^50+x^75+...) 8a) (x+x^2+x^3+...+x^10)(1+x^5+x^10+...)(1+x^10+x^20+...)(1+x^25+x^50+...) Coefficient in front of x^100 = 79. (got this by using scheme polynomial package from SICP PS-6) 8b) (x+x^2+x^3+...)(x^5+x^10+...)(x+10+x^20+...)(x^25+x^50+....) Coefficient of x^100 = 21 (got this by using scheme polynomial package from SICP PS-6) 9) See printout 10) See printout 11a) R is not an equivalence relation since it is not transitive. 11b) RoR means that we have ordered pairs {a,b} where a and b have a common co-author. 11c) Let R* be the set of ordered pairs {a,b} where a is connected to b via any number of co-authors. R* is reflexsive since {a,a} belongs to R* for every author a. R* is symmetric since {a,b} belongs to R* implies {b,a} belongs to R* because if we can trace a path of co-authors from a to b, we can re-trace the path from b to a. R* is transitive since if both {a,b} and {b,c} belongs to R* then {a,c} belongs to R* because if we can trace a path from a to b and b to c, we can also trace a path from a to c. 11d) Shai: 2 Kenneth Rosen: 3 Greenspun: 4 Ron Graham: 1 Donald Knuth: 2 Tara Holm: 3 _________________________________________________________________________ Get Your Private, Free E-mail from MSN Hotmail at http://www.hotmail.com.