Difference between revisions of "2014 AIME I Problems/Problem 3"

(Solution)
(Solution)
Line 6: Line 6:
  
 
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 if <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?"
+
Therefore, 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
+
We note there are 499 numbers between 501 and 999
 
*249 are even (divisible by 2)
 
*249 are even (divisible by 2)
 
*99 are divisible by 5
 
*99 are divisible by 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 are not divisible by neither 2 or 5 so our answer is <math>200</math>
+
<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>

Revision as of 17:37, 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 if $\dfrac{1000}{m}$ isn't, which is equivalent to m not being divisible by 2 or 5. Therefore, 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 either $2$ or $5$ so our answer is $\boxed{200}$