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)
(→‎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> 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>
+
We note that <math>\dfrac{n}{m} =\dfrac{1000-m}{m}=\dfrac{1000}{m}-1</math>
 
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.
 
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?"
 
so the question is equivalent to "how many numbers between 501 and 999 are not divisible by neither 2 or 5?"
Line 16: Line 16:
 
Using Principle of Inclusion Exclusion (PIE):
 
Using Principle of Inclusion Exclusion (PIE):
 
we get:
 
we get:
−
<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>
+
<math>499-249-99+49=200</math> numbers between 501 and 999 are not divisible by neither 2 or 5 so our answer is <math>200</math>

Revision as of 17:36, 14 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$ but we also need $\dfrac{n}{m}$ to be irreducible.

We note that $\dfrac{n}{m} =\dfrac{1000-m}{m}=\dfrac{1000}{m}-1$ hence $\dfrac{n}{m}$ is irreducible iff $\dfrac{1000}{m}$ 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

  • 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): we get: $499-249-99+49=200$ numbers between 501 and 999 are not divisible by neither 2 or 5 so our answer is $200$

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