Difference between revisions of "2014 AIME I Problems/Problem 3"
(→Solution) |
(→Solution) |
||
Line 6: | Line 6: | ||
We note that <math>\dfrac{n}{m} =\dfrac{1000-m}{m}=\dfrac{1000}{m}-1</math> | We note that <math>\dfrac{n}{m} =\dfrac{1000-m}{m}=\dfrac{1000}{m}-1</math> | ||
− | hence <math>\dfrac{n}{m}</math> is irreducible | + | hence <math>\dfrac{n}{m}</math> is irreducible if <math>\dfrac{1000}{m}</math> isn't, which is equivalent to m not being divisible by 2 or 5. |
− | + | Therefore, 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) | *249 are even (divisible by 2) | ||
*99 are divisible by 5 | *99 are divisible by 5 | ||
Line 16: | Line 16: | ||
Using Principle of Inclusion Exclusion (PIE): | Using Principle of Inclusion Exclusion (PIE): | ||
we get: | we get: | ||
− | < | + | <cmath>499-249-99+49=200</cmath> numbers between <math>501</math> and <math>999</math> are not divisible by either <math>2</math> or <math>5</math> so our answer is <math>\boxed{200}</math> |
Revision as of 16:37, 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 if
isn't, which is equivalent to m not being divisible by 2 or 5.
Therefore, 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
and
are not divisible by either
or
so our answer is