Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

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

(→‎Solution)
m (→‎Solution 2)
 
(55 intermediate revisions by 23 users not shown)
Line 1: Line 1:
 
== Problem 3 ==
 
== Problem 3 ==
−
Find the number of rational numbers <math>r,</math> <math>0<r<1,</math> such that when <math>r</math> is written as a fraction in lowest terms, the numerator and the denominator have a sum of 1000.
+
Find the number of rational numbers <math>r</math>, <math>0<r<1</math>, such that when <math>r</math> 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 <math>\dfrac{1}{999}</math> to <math>\dfrac{499}{501}</math> where each each element <math>\dfrac{n}{m}</math> has <math>n+m =1000</math> but we also need <math>\dfrac{n}{m}</math> to be irreducible
 
  
−
we note that <math>\dfrac{n}{m} =\dfrac{1000-m}{m}=\dfrac{1000}{m}-1</math>
+
== Solution 1 (Euclidean algorithm, fast)==
−
hence <math>\dfrac{n}{m}</math> is irreducible iff <math>\dfrac{1000}{m}</math> 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
+
Let the numerator and denominator <math>x,y</math> with <math>\gcd(x,y)=1</math> and <math>x+y = 1000.</math> Now if <math>\gcd(x,y) = 1</math> then <math>\gcd(x,y) =\gcd(x,1000-x)= \gcd(x,1000-x-(-1)x)=\gcd(x,1000)=1.</math> Therefore any pair that works satisfies <math>\gcd(x,1000)= 1.</math> By Euler's totient theorem, there are <math>\phi(1000) = 400</math> numbers relatively prime to 1000 from 1 to 1000. Recall that <math>r=\frac{x}{y}<1</math> and note by Euclidean algorithm <math>\gcd(1000,1000-x)=1</math>, so we want <math>x<y=1000-x.</math> Thus the <math>400</math> relatively prime numbers can generate <math>\boxed{200}</math> desired fractions.
−
*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):
+
== Solution 2==
−
we get:
+
If the initial manipulation is not obvious, consider the Euclidean Algorithm. Instead of using <math>\frac{n}{m}</math> as the fraction to use the Euclidean Algorithm on, we can rewrite this as <math>\frac{500-x}{500+x}</math> or <cmath>\gcd(500+x,500-x)=\gcd((500+x)+(500-x),500-x)=\gcd(1000,500-x).</cmath> Thus, we want <math>\gcd(1000,500-x)=1</math>. You can either proceed as Solution <math>1</math>, or consider that no even numbers work, limiting us to <math>250</math> choices of numbers and restricting <math>x</math> to be odd. If <math>x</math> is odd, <math>500-x</math> is odd, so the only possible common factors <math>1000</math> and <math>500-x</math> can share are multiples of <math>5</math>. Thus, we want to avoid these. There are <math>50</math> odd multiples of <math>5</math> less than <math>500</math>, so the answer is <math>250-50=\boxed{200}</math>.
−
<math>499-249-99+49=200</math> numbers between 501 and 999 arent divisible by neither 2 or 5 so our answer is <math>200</math>
+
 
 +
==Solution 3==
 +
Say <math>r=\frac{d}{1000-d}</math>; then <math>1\leq d\leq499</math>. If this fraction is reducible, then the modulus of some number for <math>d</math> is the same as the modulus for <math>1000-d</math>. Since <math>1000=2^3\cdot5^3</math>, that modulus can only be <math>2</math> or <math>5</math>. This implies that if <math>d\mid2</math> or <math>d\mid5</math>, the fraction is reducible. There are <math>249</math> cases where <math>d\mid2</math>, <math>99</math> where <math>d\mid5</math>, and <math>49</math> where <math>d\mid(2\cdot5=10)</math>, so by PIE, the number of fails is <math>299</math>, so our answer is <math>\boxed{200}</math>.
 +
 
 +
==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 <math>5</math> because the denominator would also be a multiple of <math>5</math>. Proceed by listing out all the other possible fractions and we realize that the numerator and denominator are always relatively prime. We have <math>499</math> fractions to start with, and <math>250</math> with odd numerators. Subtract <math>50</math> to account for the multiples of <math>5</math>, and we get <math>\boxed{200}</math>.
 +
 
 +
== Solution 5 ==
 +
We know that the set of these rational numbers is from <math>\dfrac{1}{999}</math> to <math>\dfrac{499}{501}</math> where each each element <math>\dfrac{n}{m}</math> has <math>n+m =1000</math> and <math>\dfrac{n}{m}</math> is irreducible.
 +
 
 +
We note that <math>\dfrac{n}{m} =\dfrac{1000-m}{m}=\dfrac{1000}{m}-1</math>.
 +
Hence, <math>\dfrac{n}{m}</math> is irreducible if <math>\dfrac{1000}{m}</math> is irreducible, and <math>\dfrac{1000}{m}</math> is irreducible if <math>m</math> is not divisible by <math>2</math> or <math>5</math>. Thus, the answer to the question is the number of integers between <math>501</math> and <math>999</math> inclusive that are not divisible by <math>2</math> or <math>5</math>.
 +
 
 +
We note there are <math>499</math> numbers between <math>501</math> and <math>999</math>, and
 +
*<math>249</math> numbers are divisible by <math>2</math>
 +
*<math>99</math> numbers are divisible by <math>5</math>
 +
*<math>49</math> numbers are divisible by <math>10</math>
 +
Using the Principle of Inclusion and Exclusion, we get that there are <math>499-249-99+49=200</math> 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>.
 +
 
 +
Euler's Totient Function can also be used to arrive at <math>400</math> numbers relatively prime to <math>1000</math>, meaning <math>200</math> possible fractions satisfying the necessary conditions. Solution 1 is a more detailed solution utilizing Euler's totient.
 +
 
 +
== Solution 6 ==
 +
We notice that there are a total of <math>400</math> fractions that are in simplest form where the numerator and denominator add up to <math>1000</math>. Because the numerator and denominator have to be relatively prime, there are <math>\varphi(1000)=400</math> fractions. Half of these are greater than <math>1</math>, so the answer is <math>400\div2=\boxed{200}</math>
 +
 
 +
- bedwarsnoob
 +
 
 +
~MathFun1000 (Minor Edits)
 +
 
 +
== Solution 7 ==
 +
 
 +
Our fraction can be written in the form <math>\frac{1000 - a}{a} = \frac{1000}{a} - 1.</math> Thus the fraction is reducible when <math>a</math> divides <math>1000.</math> We also want <math>500 < a < 1000.</math> By [[PIE]], the total values of <math>a</math> that make the fraction reducible is,
 +
<cmath>249 + 99 - 49 = 299.</cmath>
 +
By [[complementary counting]], the answer we want is <math>499 - 299 = \boxed{200}.</math>
 +
 
 +
==Solution 8 (Simplest)==
 +
Suppose our fraction is <math>\frac{a}{b}</math>. The given condition means <math>a+b=1000</math>. Now, if <math>a</math> and <math>b</math> share a common factor greater than <math>1</math>, then the expression <math>a+b</math> must also contain that common factor. This means our fraction cannot have a factor of <math>5</math> or be even.
 +
 
 +
There are <math>250</math> fractions that aren’t even. From this, <math>50</math> are divisible by <math>5</math>, which means the answer is <math>250-50=\boxed{200}</math>
 +
 
 +
~Geometry285
 +
 
 +
== See also ==
 +
{{AIME box|year=2014|n=I|num-b=2|num-a=4}}
 +
{{MAA Notice}}

Latest revision as of 13:17, 27 December 2023

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 (Euclidean algorithm, fast)

Let the numerator and denominator $x,y$ with $\gcd(x,y)=1$ and $x+y = 1000.$ Now if $\gcd(x,y) = 1$ then $\gcd(x,y) =\gcd(x,1000-x)= \gcd(x,1000-x-(-1)x)=\gcd(x,1000)=1.$ Therefore any pair that works satisfies $\gcd(x,1000)= 1.$ By Euler's totient theorem, there are $\phi(1000) = 400$ numbers relatively prime to 1000 from 1 to 1000. Recall that $r=\frac{x}{y}<1$ and note by Euclidean algorithm $\gcd(1000,1000-x)=1$, so we want $x<y=1000-x.$ Thus the $400$ relatively prime numbers can generate $\boxed{200}$ desired fractions.

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$ odd 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

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 1 is a more detailed solution utilizing Euler's totient.

Solution 6

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

- bedwarsnoob

~MathFun1000 (Minor Edits)

Solution 7

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 8 (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

See also

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

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2014_AIME_I_Problems/Problem_3&oldid=208497"