Massachusetts Institute of Technology 6.042J/18.062J, Fall ’05: Mathematics for Computer Science October 12 Prof. Albert R. Meyer and Prof. Ronitt Rubinfeld revised October 11, 2005, 699 minutes In-Class Problems Week 6, Wed. Problem 1. This problem lets you practice proving simple facts about divisibility. (a) Prove: If a b and a | c, then a sb + tc for all s, t.| | (b) A number is perfect if it is equal to the sum of its positive divisors, other than itself. For example, 6 is perfect, because 6 = 1 + 2 + 3. Similarly, 28 is perfect, because 28 = 1 + 2 + 4 + 7 + 14. Explain why 2k−1(2k − 1) is perfect if 2k − 1 is prime. Copyright © 2005, Prof. Albert R. Meyer and Prof. Ronitt Rubinfeld.2 In-Class Problems Week 6, Wed. Problem 2. Suppose that we have water jugs with capacities a and b. Use induction to prove that the amount of water in each jug is always a linear combination of a and b and at least one jug is either empty or full. Recall that the allowable operations are to fill a jug with water, empty a jug onto the sidewalk, or to transfer water from one jug to another until one the first one is empty or the second one is full. In Die Hard 6, the water jugs have capacities 3 and 6 gallons, and Bruce must form 4 gallons of water. As a corollary to the above, prove that Bruce dies. Problem 3. Prove: Every common divisor of a and b divides gcd(a, b). Problem 4. There is a pond. Inside the pond there are n pebbles, arranged in a cycle. A frog is sitting on one of the pebbles. Whenever he jumps, he lands exactly k pebbles away in the clockwise direction, where 0 < k < n. The frog’s meal, a delicious worm, lies on the pebble right next to his, in the clockwise direction. (a) Describe a situation where the frog can’t reach the worm. (b) In a situation where the frog can actually reach the worm, explain how to use the Pulverizer (see the appendix of this handout for a description of the Pulverizer) to find how many jumps the frog will need. (c) Compute the number of jumps if n = 50 and k = 21. Anything strange? A Appendix: The Pulverizer Euclid’s algorithm for finding the GCD of two numbers relies on repeated application of the equa-tion: gcd(a, b) = gcd(b, a rem b)3 In-Class Problems Week 6, Wed. For example, we can compute the GCD of 259 and 70 as follows: gcd(259, 70) = gcd(70, 49) since 259 rem 70 = 49 = gcd(49, 21) since 70 rem 49 = 21 = gcd(21, 7) since 49 rem 21 = 7 = gcd(7, 0) since 21 rem 7 = 0 = 7. The Pulverizer goes through the same steps, but requires some extra bookkeeping along the way: as we compute gcd(a, b), we keep track of how to write each of the remainders (49, 21, and 7, in the example) as a linear combination of a and b (this is worthwhile, because our objective is to write the last nonzero remainder, which is the GCD, as such a linear combination). For our example, here is this extra bookkeeping: x y (x rem y) = x − q · y 259 70 49 = 259 − 3 70 · 70 49 21 = 70 − 1 49· = 70 − 1 · (259 − 3 · 70) = −1 259 + 4 · 70· 49 21 7 = 49 − 2 21· = (259 − 3 · 70) − 2 · (−1 259 + 4 · 70)· = 3 259 − 11 70· · 21 7 0 We began by initializing two variables, x = a and y = b. In the first two columns above, we carried out Euclid’s algorithm. At each step, we computed x rem y, which can be written in the form x − q · y. (Remember that the Division Algorithm says x = q · y + r, where r is the remainder. We get r = x − q · y by rearranging terms.) Then we replaced x and y in this equation with equivalent linear combinations of a and b, which we already had computed. After simplifying, we were left with a linear combination of a and b that was equal to the remainder as desired. The final solution is
View Full Document
Unlocking...