Difference between revisions of "2014 AIME I Problems/Problem 3"

Revision as of 19:34, 15 January 2022

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 know 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 $501$ and $999$ 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, consider the Euclidean Algorithm. Instead of using $\frac{n}{m}$ as the fraction to use the Euclidean Algorithm on, we can rewrite this as $\frac{500-x}{500+x}$ or $\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 3

Say $r=\frac{d}{1000-d}$ ; then $1\leq d\leq499$ . 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\cdot5^3$ , that modulus can only be $2$ or $5$ . This implies that if $d\mid2$ or $d\mid5$ , the fraction is reducible. There are $249$ cases where $d\mid2$ , $99$ where $d\mid5$ , and $49$ where $d\mid(2\cdot5=10)$ , so by PIE, the number of fails is $299$ , so our answer is $\boxed{200}$ .

Solution 4

We know that the numerator of the fraction cannot be even, because the denominator would also be even. We also know that the numerator cannot be a multiple of $5$ because the denominator would also be a multiple of $5$ . Proceed by listing out all the other possible fractions and we realize that the numerator and denominator are always relatively prime. We have $499$ fractions to start with, and $250$ with odd numerators. Subtract $50$ to account for the multiples of $5$ , and we get $\boxed{200}$ .

Solution 5

Let the numerator and denominator $x,y$ with $\gcd(x,y)$ and $x+y = 1000.$ Now if $\gcd(1000,x) = 1$ then $\gcd(x,1000-x) = \gcd(x,y) = 1.$ Therefore any pair that works satisfies $\gcd(x,1000)= 1.$ There are $\phi(1000) = 400$ pairs $x,y$ such that $x+y= 1000$ and $\gcd(x,y) = 1.$ However, exactly half of them work because of the condition $x<y.$ Therefore the desired answer is $\boxed{200}.$

Solution 6 (sort of cheese)

We notice that there are a total of $400$ fractions that are in simplest form and the numerator and denominator add up to $1000$ because the numerator and denominator have to be relatively prime so there are $\varphi(1000)=400$ . Half of these are greater than $1$ so the answer is $400\div2=\boxed{200}$

- bedwarsnoob

~MathFun1000 (Minor Edits)

Solution 6

Our fraction can be written in the form $\frac{1000 - a}{a} = \frac{1000}{a} - 1.$ Thus the fraction is reducible when $a$ divides $1000.$ We also want $500 < a < 1000.$ By PIE, the total values of $a$ that make the fraction reducible is, $249 + 99 - 49 = 299.$ By complementary counting, the answer we want is $499 - 299 = \boxed{200}.$

Solution 7 (Simplest)

Suppose our fraction is $\frac{a}{b}$ . The given condition means $a+b=1000$ . Now, if $a$ and $b$ share a common factor greater than $1$ , then the expression $a+b$ must also contain that common factor. This means our fraction cannot have a factor of $5$ or be even.

There are $250$ fractions that aren’t even. From this, $50$ are divisible by $5$ , which means the answer is $250-50=\boxed{200}$

~Geometry285

@@ Line 33: / Line 33: @@
 == Solution 6 (sort of cheese) ==
-We notice that there are a total of <math>400</math> fractions that are in simplest form and the numerator and denominator add up to <math>1000</math> because the numerator and denominator have to be relatively prime so there are <math>\Phi(1000)=400</math>. Half of these are greater than <math>1</math> so the answer is <math>400\div2=\boxed{200}</math>
+We notice that there are a total of <math>400</math> fractions that are in simplest form and the numerator and denominator add up to <math>1000</math> because the numerator and denominator have to be relatively prime so there are <math>\varphi(1000)=400</math>. Half of these are greater than <math>1</math> so the answer is <math>400\div2=\boxed{200}</math>
 - bedwarsnoob
+~MathFun1000 (Minor Edits)
 == Solution 6 ==

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