Difference between revisions of "2014 AIME I Problems/Problem 3"
Tempaccount (talk | contribs) (Remove extra problem section) |
Bluelinfish (talk | contribs) m (→Solution 4) |
||
| Line 27: | Line 27: | ||
==Solution 4== | ==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 | + | 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 <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 13:17, 20 December 2018
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 
.
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 249 cases where , 99 where , and 49 where 
, so by PIE, the number of fails is 299, 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 .
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. 
