Difference between revisions of "2014 AIME I Problems/Problem 3"
(→Problem 3) |
(→Solution) |
||
| Line 3: | Line 3: | ||
== Solution == | == Solution == | ||
| + | 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> but we also need <math>\dfrac{n}{m}</math> to be irreducible | ||
| + | |||
| + | we note that <math>\dfrac{n}{m} =\dfrac{1000-m}{m}=\dfrac{1000}{m}-1</math> | ||
| + | hence <math>\dfrac{n}{m}</math> is irreducible iff <math>\dfrac{1000}{m}</math> isn't, which is equivalent to m not being divisible by 2 or 5. | ||
| + | so the question is equivalent to "how many numbers between 501 and 999 are not divisible by neither 2 or 5?" | ||
| + | |||
| + | we note there are 499 numbers between 501 and 999 | ||
| + | *249 are even (divisible by 2) | ||
| + | *99 are divisible by 5 | ||
| + | *49 are divisible by 10 (both 2 and 5) | ||
| + | |||
| + | Using Principle of Inclusion Exclusion (PIE): | ||
| + | we get: | ||
| + | <math>499-249-49+49=200</math> numbers between 501 and 999 arent divisible by neither 2 or 5 so our answer is <math>200</math> | ||
Revision as of 13:28, 14 March 2014
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
We have that the set of these rational numbers is from 
to 
where each each element 
has 
but we also need to be irreducible
we note that 
hence is irreducible iff 
isn't, which is equivalent to m not being divisible by 2 or 5.
so the question is equivalent to "how many numbers between 501 and 999 are not divisible by neither 2 or 5?"
we note there are 499 numbers between 501 and 999
- 249 are even (divisible by 2)
- 99 are divisible by 5
- 49 are divisible by 10 (both 2 and 5)
Using Principle of Inclusion Exclusion (PIE):
we get:
numbers between 501 and 999 arent divisible by neither 2 or 5 so our answer is 
