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 1

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

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 $\frac{n}{m}$ as the fraction to use the euclidean algorithm on, rewrite this as $\frac{500-x}{500+x} 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 $250-50=\boxed{200}$ .

Solution Numbers

Say $r=\frac{d}{1000-d}$ ; then $1<=d<=499$ . If this fraction is reducible, then the modulus of some number for $d$ is the same as the modulus for $1000-d$ . Since $1000=2^3*5*3$ , that modulus can only be $2$ or $5$ . This implies that if $d|2$ or $d|5$ , the fraction is reducible. There are 249 cases where $d|2$ , 99 where $d|5$ , and 49 where $d|(2*5=10)$ , so by PIE, the number of fails is 299, so our answer is $\boxed{200}$ .

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

Page

Toolbox

Search

2014 AIME I Problems/Problem 3

Contents

Problem 3

Solution 1

Solution 2

Solution Numbers

See also