Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "Overcounting"

m (created counting internal link and bolded article name)
(→‎Examples)
 
(22 intermediate revisions by 14 users not shown)
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.
+
Strategic '''overcounting''' is the process of counting more than desired and then systematically "correcting" for overcounted elements by removing them from the total count via subtraction or division. The idea of strategic overcounting is fundamental to [[combinatorics]] and plays a role in incredibly important counting tools such as [[combinations]] and the [[Principle of Inclusion-Exclusion]].
  
 +
==Related Videos==
  
−
== Example AIME 1992 #5 ==
+
* [http://www.artofproblemsolving.com/Videos/external.php?video_id=59 (Counting the Number of Arrangements of Letters in a Word)]
−
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)
+
* [http://www.artofproblemsolving.com/Videos/external.php?video_id=60 (Counting pairs)]
 +
* [http://www.artofproblemsolving.com/Videos/external.php?video_id=57 (Counting Objects in a Circle Part 1)]
 +
* [http://www.artofproblemsolving.com/Videos/external.php?video_id=61 (Counting Objects in a Circle Part 2)]
 +
== More Examples ==
  
−
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;
+
* [[2004 AIME I Problems/Problem 3|AIME 2004I/3]]
−
<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)''
+
==Introductory Problems==
 +
*How many different words can be formed with the letters <math>AAAABBCCDDDPPP</math>?(Not necessarily meaningful words)  
 +
 
 +
== See also ==
 +
* [[Casework]]
 +
* [[Complementary counting]]
 +
* [[Constructive counting]]
 +
 
 +
{{stub}}
 +
[[Category:Definition]]
 +
[[Category:Combinatorics]]

Latest revision as of 22:23, 22 July 2025

Strategic overcounting is the process of counting more than desired and then systematically "correcting" for overcounted elements by removing them from the total count via subtraction or division. The idea of strategic overcounting is fundamental to combinatorics and plays a role in incredibly important counting tools such as combinations and the Principle of Inclusion-Exclusion.

Related Videos

More Examples

Introductory Problems

  • How many different words can be formed with the letters $AAAABBCCDDDPPP$?(Not necessarily meaningful words)

See also

This article is a stub. Help us out by expanding it.

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Overcounting&oldid=255058"