2014 AIME I Problems/Problem 3: Difference between revisions
| Line 2: | Line 2: | ||
Find the number of rational numbers <math>r,</math> <math>0<r<1,</math> such that when <math>r</math> is written as a fraction in lowest terms, the numerator and the denominator have a sum of 1000. | Find the number of rational numbers <math>r,</math> <math>0<r<1,</math> such that when <math>r</math> is written as a fraction in lowest terms, the numerator and the denominator have a sum of 1000. | ||
== Solution == | == Solution 1== | ||
We have that the set of these rational numbers is from <math>\dfrac{1}{999}</math> to <math>\dfrac{499}{501}</math> where each each element <math>\dfrac{n}{m}</math> has <math>n+m =1000</math> and <math>\dfrac{n}{m}</math> is irreducible. | We have that the set of these rational numbers is from <math>\dfrac{1}{999}</math> to <math>\dfrac{499}{501}</math> where each each element <math>\dfrac{n}{m}</math> has <math>n+m =1000</math> and <math>\dfrac{n}{m}</math> is irreducible. | ||
| Line 16: | Line 16: | ||
Euler's Totient Function can also be used to arrive at 400 numbers relatively prime to 1000, meaning 200 possible fractions satisfying the necessary conditions. | Euler's Totient Function can also be used to arrive at 400 numbers relatively prime to 1000, meaning 200 possible fractions satisfying the necessary conditions. | ||
== Solution 2== | |||
If the initial manipulation is not obvious, instead ,consider the euclidean algorithm. Instead of using <math>\frac{n}{m}</math> as the fraction to use the euclidean algorithm on, rewrite this as <math>\frac{500-x}{500+x}</math> gcd(500+x,500-x)=gcd((500+x)+(500-x),500-x)=gcd(1000,500-x). Thus, we want gcd(1000,500-x)=1. You can either proceed as solution 1, or consider that no even numbers work, limiting us to 250 choices of numbers and restricting x to be odd. If x is odd, 500-x is odd, so the only possible common factors 1000 and 500-x can share are multiples of 5. Thus, we want to avoid these. There are 50 multiples of 5 less than 500, so the answer is <math>250-50=\boxed{200}</math>. | |||
== See also == | == See also == | ||
{{AIME box|year=2014|n=I|num-b=2|num-a=4}} | {{AIME box|year=2014|n=I|num-b=2|num-a=4}} | ||
{{MAA Notice}} | {{MAA Notice}} | ||
Revision as of 23:32, 9 September 2015
Problem 3
Find the number of rational numbers 
such that when 
is written as a fraction in lowest terms, the numerator and the denominator have a sum of 1000.
Solution 1
We have that the set of these rational numbers is from 
to 
where each each element 
has 
and is irreducible.
We note that 
.
Hence, is irreducible if 
is irreducible, and is irreducible if 
is not divisible by 2 or 5. Thus, the answer to the question is the number of integers between 999 and 501 inclusive that are not divisible by 2 or 5.
We note there are 499 numbers between 501 and 999, and
- 249 numbers are divisible by 2
- 99 numbers are divisible by 5
- 49 numbers are divisible by 10
Using the Principle of Inclusion and Exclusion, we get that there are 
numbers between 
and 
are not divisible by either 
or 
, so our answer is 
.
Euler's Totient Function can also be used to arrive at 400 numbers relatively prime to 1000, meaning 200 possible fractions satisfying the necessary conditions.
Solution 2
If the initial manipulation is not obvious, instead ,consider the euclidean algorithm. Instead of using 
as the fraction to use the euclidean algorithm on, rewrite this as 
gcd(500+x,500-x)=gcd((500+x)+(500-x),500-x)=gcd(1000,500-x). Thus, we want gcd(1000,500-x)=1. You can either proceed as solution 1, or consider that no even numbers work, limiting us to 250 choices of numbers and restricting x to be odd. If x is odd, 500-x is odd, so the only possible common factors 1000 and 500-x can share are multiples of 5. Thus, we want to avoid these. There are 50 multiples of 5 less than 500, so the answer is 
.
See also
| 2014 AIME I (Problems • Answer Key • Resources) | ||
| Preceded by Problem 2 |
Followed by Problem 4 | |
| 1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 | ||
| All AIME Problems and Solutions | ||
These problems are copyrighted © by the Mathematical Association of America, as part of the American Mathematics Competitions. Error creating thumbnail: File missing
