Difference between revisions of "2014 AIME I Problems/Problem 3"
Mathfun1000 (talk | contribs) m |
Mathfun1000 (talk | contribs) m |
||
Line 20: | Line 20: | ||
== Solution 2== | == Solution 2== | ||
If the initial manipulation is not obvious, consider the Euclidean Algorithm. Instead of using <math>\frac{n}{m}</math> as the fraction to use the Euclidean Algorithm on, we can rewrite this as <math>\frac{500-x}{500+x}</math> or <cmath>\gcd(500+x,500-x)=\gcd((500+x)+(500-x),500-x)=\gcd(1000,500-x).</cmath> Thus, we want <math>\gcd(1000,500-x)=1</math>. You can either proceed as Solution <math>1</math>, 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>. | If the initial manipulation is not obvious, consider the Euclidean Algorithm. Instead of using <math>\frac{n}{m}</math> as the fraction to use the Euclidean Algorithm on, we can rewrite this as <math>\frac{500-x}{500+x}</math> or <cmath>\gcd(500+x,500-x)=\gcd((500+x)+(500-x),500-x)=\gcd(1000,500-x).</cmath> Thus, we want <math>\gcd(1000,500-x)=1</math>. You can either proceed as Solution <math>1</math>, 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>. | ||
+ | |||
==Solution 3== | ==Solution 3== | ||
− | Say <math>r=\frac{d}{1000-d}</math>; then <math>1\leq d\leq499</math>. If this fraction is reducible, then the modulus of some number for <math>d</math> is the same as the modulus for <math>1000-d</math>. Since <math>1000=2^3\cdot5^3</math>, that modulus can only be <math>2</math> or <math>5</math>. This implies that if <math>d\ | + | Say <math>r=\frac{d}{1000-d}</math>; then <math>1\leq d\leq499</math>. If this fraction is reducible, then the modulus of some number for <math>d</math> is the same as the modulus for <math>1000-d</math>. Since <math>1000=2^3\cdot5^3</math>, that modulus can only be <math>2</math> or <math>5</math>. This implies that if <math>d\mid2</math> or <math>d\mid5</math>, the fraction is reducible. There are <math>249</math> cases where <math>d\mid2</math>, <math>99</math> where <math>d\mid5</math>, and <math>49</math> where <math>d\mid(2\cdot5=10)</math>, so by PIE, the number of fails is <math>299</math>, so our answer is <math>\boxed{200}</math>. |
Revision as of 20:29, 15 January 2022
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 know 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
or
. Thus, the answer to the question is the number of integers between
and
inclusive that are not divisible by
or
.
We note there are numbers between
and
, and
numbers are divisible by
numbers are divisible by
numbers are divisible by
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 numbers relatively prime to
, meaning
possible fractions satisfying the necessary conditions.
Solution 2
If the initial manipulation is not obvious, consider the Euclidean Algorithm. Instead of using as the fraction to use the Euclidean Algorithm on, we can rewrite this as
or
Thus, we want
. You can either proceed as Solution
, 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
.
Solution 3
Say ; then
. If this fraction is reducible, then the modulus of some number for
is the same as the modulus for
. Since
, that modulus can only be
or
. This implies that if
or
, the fraction is reducible. There are
cases where
,
where
, and
where
, so by PIE, the number of fails is
, so our answer is
.
Solution 4
We know that the numerator of the fraction cannot be even, because the denominator would also be even. We also know that the numerator cannot be a multiple of 5 because the denominator would also be a multiple of 5. Proceed by listing out all the other possible fractions and we realize that the numerator and denominator are always relatively prime. We have 499 fractions to start with, and 250 with odd numerators. Subtract 50 to account for the multiples of 5, and we get .
Solution 5
Let the numerator and denominator with
and
Now if
then
Therefore any pair that works satisfies
There are
pairs
such that
and
However, exactly half of them work because of the condition
Therefore the desired answer is
Solution 6 (sort of cheese)
We notice that there are a total of fractions that are in simplest form and the numerator and denominator add up to
because the numerator and denominator have to be relatively prime so there are
. Half of these are greater than
so the answer is
- bedwarsnoob
Solution 6
Our fraction can be written in the form Thus the fraction is reducible when
divides
We also want
By PIE, the total values of
that make the fraction reducible is,
By complementary counting, the answer we want is
Solution 7 (Simplest)
Suppose our fraction is . The given condition means
. Now, if
and
share a common factor greater than
, then the expression
must also contain that common factor. This means our fraction cannot have a factor of
or be even.
There are fractions that aren’t even. From this,
are divisible by
, which means the answer is
~Geometry285
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.