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"

m
m (→‎Solution 2)
 
(22 intermediate revisions by 2 users not shown)
Line 2: Line 2:
 
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 1==
 
−
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> and <math>\dfrac{n}{m}</math> is 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 if <math>\dfrac{1000}{m}</math> is irreducible, and <math>\dfrac{1000}{m}</math> is irreducible if <math>m</math> 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
+
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 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 <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 400 numbers relatively prime to 1000, meaning 200 possible fractions satisfying the necessary conditions.
 
 
== Solution 2==
 
== Solution 2==
−
If the initial manipulation is not obvious, instead ,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> <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 1, 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> multiples of <math>5</math> less than <math>500</math>, so the answer is <math>250-50=\boxed{200}</math>.
+
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>.
  
 
==Solution 3==
 
==Solution 3==
−
Say <math>r=\frac{d}{1000-d}</math>; then <math>1<=d<=499</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*5^3</math>, that modulus can only be <math>2</math> or <math>5</math>. This implies that if <math>d|2</math> or <math>d|5</math>, the fraction is reducible. There are 249 cases where <math>d|2</math>, 99 where <math>d|5</math>, and 49 where <math>d|(2*5=10)</math>, so by PIE, the number of fails is 299, so our answer is <math>\boxed{200}</math>.
+
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==
 
==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 <math>\boxed{200}</math>.
+
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.
  
−
== Solution 5 ==
+
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>.
  
−
Let the numerator and denominator <math>x,y</math> with <math>\gcd(x,y)</math> and <math>x+y = 1000.</math> Now if <math>\gcd(1000,x) = 1</math> then <math>\gcd(x,1000-x) = \gcd(x,y) = 1.</math> Therefore any pair that works satisfies <math>\gcd(x,1000)= 1.</math> There are <math>\phi(1000) = 400</math> pairs <math>x,y</math> such that <math>x+y= 1000</math> and <math>\gcd(x,y) = 1.</math> However, exactly half of them work because of the condition <math>x<y.</math> Therefore the desired answer is <math>\boxed{200}.</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 (sort of cheese) ==
+
== Solution 6 ==
−
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/2=200</math>
+
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
 
- bedwarsnoob
  
−
== Solution 6 ==
+
~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,  
 
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,  
Line 47: Line 44:
 
By [[complementary counting]], the answer we want is <math>499 - 299 = \boxed{200}.</math>
 
By [[complementary counting]], the answer we want is <math>499 - 299 = \boxed{200}.</math>
  
−
==Solution 7 (Simplest)==
+
==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.
 
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.
  

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"