2014 AIME I Problems/Problem 3

Problem 3

Find the number of rational numbers $r,$ $0<r<1,$ such that when $r$ 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 $\dfrac{1}{999}$ to $\dfrac{499}{501}$ where each each element $\dfrac{n}{m}$ has $n+m =1000$ but we also need $\dfrac{n}{m}$ to be irreducible.

We note that $\dfrac{n}{m} =\dfrac{1000-m}{m}=\dfrac{1000}{m}-1$ hence $\dfrac{n}{m}$ is irreducible if $\dfrac{1000}{m}$ 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: $499-249-99+49=200$ numbers between $501$ and $999$ are not divisible by either $2$ or $5$ so our answer is $\boxed{200}$

Page

Toolbox

Search

2014 AIME I Problems/Problem 3

Problem 3

Solution