Difference between revisions of "2014 AIME I Problems/Problem 3"
m (→Solution 2) |
Shell769324 (talk | contribs) m (→Solution 2) |
||
Line 17: | Line 17: | ||
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. | 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. | ||
== Solution 2== | == Solution 2== | ||
− | If the initial manipulation is not obvious, instead ,consider the euclidean algorithm. Instead of using <math>\frac{n}{m}</math> as the fraction to use the euclidean algorithm on, rewrite this as <math>\frac{500-x}{500+x} gcd(500+x,500-x)=gcd((500+x)+(500-x),500-x)=gcd(1000,500-x)</math>. Thus, we want gcd(1000,500-x)=1. You can either proceed as solution 1, or consider that no even numbers work, limiting us to 250 choices of numbers and restricting x to be odd. If x is odd, 500-x is odd, so the only possible common factors 1000 and 500-x can share are multiples of 5. Thus, we want to avoid these. There are 50 multiples of 5 less than 500, so the answer is <math>250-50=\boxed{200}</math>. | + | If the initial manipulation is not obvious, instead ,consider the euclidean algorithm. Instead of using <math>\frac{n}{m}</math> as the fraction to use the euclidean algorithm on, rewrite this as <math>\frac{500-x}{500+x} gcd(500+x,500-x)=gcd((500+x)+(500-x),500-x)=gcd(1000,500-x)</math>. Thus, we want <math>gcd(1000,500-x)=1</math>. You can either proceed as solution 1, or consider that no even numbers work, limiting us to <math>250</math> choices of numbers and restricting <math>x</math> to be odd. If <math>x</math> is odd, <math>500-x</math> is odd, so the only possible common factors <math>1000</math> and <math>500-x</math> can share are multiples of <math>5</math>. Thus, we want to avoid these. There are <math>50</math> multiples of <math>5</math> less than <math>500</math>, so the answer is <math>250-50=\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, 25 February 2017
Contents
Problem 3
Find the number of rational numbers
such that when
is written as a fraction in lowest terms, the numerator and the denominator have a sum of 1000.
Solution 1
We have that the set of these rational numbers is from to
where each each element
has
and
is irreducible.
We note that .
Hence,
is irreducible if
is irreducible, and
is irreducible if
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 numbers between
and
are not divisible by either
or
, so our answer is
.
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.
Solution 2
If the initial manipulation is not obvious, instead ,consider the euclidean algorithm. Instead of using as the fraction to use the euclidean algorithm on, rewrite this as
. Thus, we want
. You can either proceed as solution 1, or consider that no even numbers work, limiting us to
choices of numbers and restricting
to be odd. If
is odd,
is odd, so the only possible common factors
and
can share are multiples of
. Thus, we want to avoid these. There are
multiples of
less than
, so the answer is
.
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.