Difference between revisions of "Overcounting"
(→Example) |
|||
| Line 3: | Line 3: | ||
== Example == | == Example == | ||
| − | Let S be the set of all rational numbers <math>{r}</math>, <math>0 < r < 1</math>, that have a repeating decimal expansion in the form <math>0.abcabcabc\dots</math>, where the digits a, b, and c are not necessarily distinct. To write the elements of S as fractions in lowest terms, how many numerators are required? | + | Let S be the set of all rational numbers <math>{r}</math>, <math>0 < r < 1</math>, that have a repeating decimal expansion in the form <math>0.abcabcabc\dots</math>, where the digits a, b, and c are not necessarily distinct. To write the elements of S as fractions in lowest terms, how many numerators are required? ([[AIME]] 1992 #5) |
| − | ''( | + | All repeating fractions can be expressed as a number over 999. Hence, there are <math>10*10*10 - 1 = 999</math> possibilities (since we cannot have zero). We know, however, that some of these numerators have common factors with 999 and will, therefore, be reduced, so we must subtract them from our original count. The prime factorization of 999 is $3^3*37$, so we need to subtract all multiples of 3 and 37; |
| + | <br><center><math>999 - 333 - 27 = 639</math></center><br> | ||
| + | But, we have subtracted the multiples of <math>37*3</math> twice so we must add them back and also we have subtracted the multiples of <math>3^4</math> which will produce unique numerators so we need to add them back as well. Our final number is thus, | ||
| + | <br><center><math>639 + 9 + 12 = 660</math></center><br> | ||
| + | |||
| + | ''(This seems to be more inclusion exclusion but it was the best example I could find)'' | ||
Revision as of 22:37, 18 June 2006
Description
Overcounting is the process of counting more than what you need and then systematically subtracting the parts which do not belong.
Example
Let S be the set of all rational numbers 
, 
, that have a repeating decimal expansion in the form 
, where the digits a, b, and c are not necessarily distinct. To write the elements of S as fractions in lowest terms, how many numerators are required? (AIME 1992 #5)
All repeating fractions can be expressed as a number over 999. Hence, there are 
possibilities (since we cannot have zero). We know, however, that some of these numerators have common factors with 999 and will, therefore, be reduced, so we must subtract them from our original count. The prime factorization of 999 is $3^3*37$, so we need to subtract all multiples of 3 and 37;
But, we have subtracted the multiples of 
twice so we must add them back and also we have subtracted the multiples of 
which will produce unique numerators so we need to add them back as well. Our final number is thus,
(This seems to be more inclusion exclusion but it was the best example I could find)
