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)
Line 3: Line 3:
  
 
== Solution ==
 
== 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 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>
+
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> isn't, which is equivalent to m not being divisible by 2 or 5.
+
Hence, <math>\dfrac{n}{m}</math> is irreducible if <math>\dfrac{1000}{m}</math> is irriducible, and <math>\dfrac{1000}{m}</math> is irriducible 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.
−
Therefore, the question is equivalent to "how many numbers between 501 and 999 are not divisible by either 2 or 5?"
 
  
−
We note there are 499 numbers between 501 and 999
+
We note there are 499 numbers between 501 and 999, and
−
*249 are even (divisible by 2)
+
*249 are divisible by 2
 
*99 are divisible by 5
 
*99 are divisible by 5
−
*49 are divisible by 10 (both 2 and 5)
+
*49 are divisible by 10
  
−
Using Principle of Inclusion Exclusion (PIE):
+
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>.
−
we get:
 
−
<cmath>499-249-99+49=200</cmath> 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>
 
  
 
== See also ==
 
== See also ==
 
{{AIME box|year=2014|n=I|num-b=2|num-a=4}}
 
{{AIME box|year=2014|n=I|num-b=2|num-a=4}}
 
{{MAA Notice}}
 
{{MAA Notice}}

Revision as of 13:57, 15 March 2014

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 irriducible, and $\dfrac{1000}{m}$ is irriducible 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 are divisible by 2
  • 99 are divisible by 5
  • 49 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}$.

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