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 iff $\dfrac{1000}{m}$ 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: $499-249-99+49=200$ numbers between 501 and 999 arent divisible by neither 2 or 5 so our answer is $200$

Page

Toolbox

Search

2014 AIME I Problems/Problem 3

Problem 3

Solution