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 (→‎Solution Numbers)
(→‎Solution Numbers)
Line 19: Line 19:
 
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, rewrite this as <math>\frac{500-x}{500+x} gcd(500+x,500-x)=gcd((500+x)+(500-x),500-x)=gcd(1000,500-x)</math>. 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, instead ,consider the euclidean algorithm. Instead of using <math>\frac{n}{m}</math> as the fraction to use the euclidean algorithm on, rewrite this as <math>\frac{500-x}{500+x} gcd(500+x,500-x)=gcd((500+x)+(500-x),500-x)=gcd(1000,500-x)</math>. 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>.
  
−
==Solution Numbers==
+
==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<=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>.
  

Revision as of 17:15, 20 February 2018

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 3

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}$.

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=92143"