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)
(→‎Solution)
Line 9: Line 9:
  
 
We note there are 499 numbers between 501 and 999, and
 
We note there are 499 numbers between 501 and 999, and
−
*249 are divisible by 2
+
*249 numbers are divisible by 2
−
*99 are divisible by 5
+
*99 numbers are divisible by 5
−
*49 are divisible by 10
+
*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>.
 
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>.

Revision as of 02:02, 9 May 2015

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

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.

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