|
|
| Line 1: |
Line 1: |
| | '''Overcounting''' is the process of [[counting more]] than what you need and then systematically subtracting the parts which do not belong. | | '''Overcounting''' is the process of [[counting more]] than what you need and then systematically subtracting the parts which do not belong. |
| | | | |
| | + | == Examples == |
| | | | |
| − | == Example AIME 1992 #5 ==
| + | * [http://www.artofproblemsolving.com/Forum/resources.php?c=182&cid=45&year=2004&p=377949 AIME 2004I/3) |
| − | 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 09:33, 19 June 2006
Overcounting is the process of counting more than what you need and then systematically subtracting the parts which do not belong.
Examples
