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 14: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 (ProblemsAnswer KeyResources)
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