Find Pairs of Positive Integers
Date: 10/15/2001 at 15:50:21 From: Mike Subject: Brain busters With each entry I submit, I have to write a different pair of positive integers whose greatest common factor is 1 and whose sum is 2000. (Pairs differing in the order of addition are counted as 1 pair, not as 2 different pairs.) For example, I submit the pair (1, 1999) with my first entry. With these restrictions, at most how many entries can one person submit?
Date: 10/15/2001 at 16:20:37 From: Doctor Jubal Subject: Re: Brain busters Hi Mike, Here's the beginning of a solution. I'll leave you to figure out the rest. There are 1000 ways we could add two numbers to get 2000. The first one is 1+1999, the 2nd one is 2+1998, and so forth until we get to 1000+1000. Not all of them count, though, because in some of them, the two numbers share a common factor. Let's call this common factor f, and write the two numbers as a*f and b*f. Then a*f + b*f = (a+b)*f = 2000. That is to say, if the two numbers share a common factor, 2000 must also share that factor. But 2000 has a lot of factors, and it would be tedious to look at each pair of numbers and each of the factors of 2000 and see if the numbers are divisible by that factor of 2000. The good news is we don't have to look at all the factors. Let's say that f is composite and can be factored into primes like this: f = p1^n1 * p2^n2 * p3^n3 * ... Then we can rewrite the two numbers a*f = a * p1^n1 * p2^n2 * ... b*f = b * p1^n1 * p2^n2 * ... That is to say, if the two numbers share a composite factor, they must also share a prime factor. The whole point of this is that we don't have to consider any of 2000's composite factors, because any pairs of numbers we would rule out with a composite factor, we can also rule out with a prime factor. So, let's find the prime factors of 2000 2000 = 2 * 1000 = 2 * 10^3 = 2 * (2*5)^3 = 2^4 * 5^3. We see that 2 and 5 are the only prime factors of 2000. Now, your task is to figure out (1) of the 1000 ways to add two positive numbers and get 2000, in how many of them are both numbers divisible by 2? (2) in how many of them are both numbers divisible by 5? (3) in how many of them are both numbers divisible by both 2 and 5? Then, from the 1000 ways, you can subtract all the number of ways where the numbers are divisible by 2, and you can also subtract the number of ways where the numbers are divisble by 5. But now, you've just subtracted any ways where the numbers are divisible by both 2 and 5 twice, so you have to add that many ways back in to correct that mistake. And voila, you have an answer. Does this help? Write back if you'd like to talk about this some more, or if you have any other questions. - Doctor Jubal, The Math Forum http://mathforum.org/dr.math/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994-2013 The Math Forum