Difference between revisions of "Overcounting"

m (changed section name for aime problem)
m (created counting internal link and bolded article name)
Line 1: Line 1:
== Description ==
+
'''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.
 
  
  

Revision as of 01:22, 19 June 2006

Overcounting is the process of counting more than what you need and then systematically subtracting the parts which do not belong.


Example AIME 1992 #5

Let S be the set of all rational numbers ${r}$, $0 < r < 1$, that have a repeating decimal expansion in the form $0.abcabcabc\dots$, 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 $10*10*10 - 1 = 999$ 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;


$999 - 333 - 27 = 639$


But, we have subtracted the multiples of $37*3$ twice so we must add them back and also we have subtracted the multiples of $3^4$ which will produce unique numerators so we need to add them back as well. Our final number is thus,


$639 + 9 + 12 = 660$


(This seems to be more inclusion exclusion but it was the best example I could find)