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"
 
(5 intermediate revisions by 5 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]].
−
 
 
−
The [[Principle of Inclusion-Exclusion]] (PIE) is a systematic method of repeated overcounting that is a tool in solving many [[combinatorics]] problems.
 
  
 
==Examples==
 
==Examples==
Line 9: Line 7:
 
"How many numbers less than or equal to 100 are divisible by either 2 or 3?"
 
"How many numbers less than or equal to 100 are divisible by either 2 or 3?"
  
−
Solution: Clearly, there are 50 numbers less than 100 that are divisible by 2, and 33 that are divisible by 3. However, we note that we overcount several numbers, such as 12, which is divisible by both 2 and 3. To correct for this overcounting, we must subtract out the numbers that are divisible by both 2 and 3, as we have counted them twice. A number that is divisible by both 2 and 3 must be divisible by 6, and there are 16 such numbers. Thus, there are <math>50+33-16=\boxed{67}</math> numbers that are divisible by either 2 or 3.  
+
Solution: Clearly, there are 50 numbers less than 100 that are divisible by 2 and 33 that are divisible by 3. However, we note that we overcount several numbers, such as 12, which is divisible by both 2 and 3. To correct for this overcounting, we must subtract out the numbers that are divisible by both 2 and 3, as we have counted them twice. A number that is divisible by both 2 and 3 must be divisible by 6, and there are 16 such numbers. Thus, there are <math>50+33-16=\boxed{67}</math> numbers that are divisible by either 2 or 3.  
−
(Note that it is not a coincidence that 67 is close to 2 thirds of 100! We can approach this problem in a constructive way, building the set based on the remainders when divided by 3, but that is a different subject).  
+
(Note that it is not a coincidence that 67 is close to two-thirds of 100! We can approach this problem in a constructive way, building the set based on the remainders when divided by 3, but that is a different subject).  
  
 
Another basic example is combinations. In these, we correct for overcounting with division, by dividing out what we overcount (as opposed to above where we subtracted it out).  
 
Another basic example is combinations. In these, we correct for overcounting with division, by dividing out what we overcount (as opposed to above where we subtracted it out).  
Line 18: Line 16:
 
"How many numbers less than or equal to 100 are divisible by 2 or 3 but not 4?".
 
"How many numbers less than or equal to 100 are divisible by 2 or 3 but not 4?".
  
−
Now see we have another type of overcounting.For example, we have <math>n</math> people in a party and everyone will handshake with each other.Suppose we are given a order to count the number of handshakes.Its not a matter of great deal if there are less than 10 persons.But assume a party from the President, there will be millions of people.Now the task seems impossible without mathematics.Suppose we know the total number of people invited in the party, say <math>n</math>.
+
Now see we have another type of overcounting. For example, we have <math>n</math> people at a party and everyone will handshake with each other. Suppose we are given an order to count the number of handshakes. It's not a matter of a great deal if there are less than 10 persons. But assume a party from the President, there will be millions of people. Now the task seems impossible without mathematics. Suppose we know the total number of people invited to the party, say <math>n</math>.
  
−
One person will handshake with all other except himself,i.e, he will handshake with <math>n-1</math> people.Now since the total of people in the party is <math>n</math>.So there will be <math>n*(n-1)</math> handshakes.Now lets try our formula for two people.According to the formula we get 2 handshakes, but wait,we will have only 1 handshake between two persons.That means we have overcounted somewhere.
+
One person will handshake with all others except himself,i.e, he will handshake with <math>n-1</math> people.Now since the total of people in the party is <math>n</math>.So there will be <math>n*(n-1)</math> handshakes. Now let's try our formula for two people. According to the formula we get 2 handshakes, but wait, we will have only 1 handshake between two persons. That means we have overcounted somewhere.
  
−
Actually, we counted 1 handshakes twice for the two persons.In our formula we have overcounted each handshake twice.One handshake for Person A to Person B and another for Person B to person A.So basically, <math>2h = n*(n-1) \implies h = \frac{n*(n-1)}{2}</math> where h is the number of handshakes.Now our formula tally with our experiment results.(To easily solve a problem, we overcount and then divide with number of times we overcounted)     
+
Actually, we counted 1 handshake twice for the two persons. In our formula, we have overcounted each handshake twice. One handshake for Person A to Person B and another for Person B to person A.So basically, <math>2h = n*(n-1) \implies h = \frac{n*(n-1)}{2}</math> where h is the number of handshakes. Now our formula tally with our experiment results. (To easily solve a problem, we overcount and then divide with number of times we overcounted)     
  
 
Here is a question to try:
 
Here is a question to try:
  
−
"How many diagonals does a n-sided polygon have?"
+
"How many diagonals does an n-sided polygon have?????"
 
Answer to the question and lots more is given in this [http://www.artofproblemsolving.com/Videos/external.php?video_id=58 (video)]
 
Answer to the question and lots more is given in this [http://www.artofproblemsolving.com/Videos/external.php?video_id=58 (video)]
 
Other examples of overcounting are shown in the videos below.
 
Other examples of overcounting are shown in the videos below.
 +
 
==Related Videos==
 
==Related Videos==
  
Line 35: Line 34:
 
* [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=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)]
 
* [http://www.artofproblemsolving.com/Videos/external.php?video_id=61 (Counting Objects in a Circle Part 2)]
−
== Examples ==
+
== More Examples ==
  
 
* [[2004 AIME I Problems/Problem 3|AIME 2004I/3]]
 
* [[2004 AIME I Problems/Problem 3|AIME 2004I/3]]
 +
 
==Introductory Problems==
 
==Introductory Problems==
 
*How many different words can be formed with the letters <math>AAAABBCCDDDPPP</math>?(Not necessarily meaningful words)  
 
*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}}
 
{{stub}}
 
[[Category:Definition]]
 
[[Category:Definition]]
 
[[Category:Combinatorics]]
 
[[Category:Combinatorics]]

Latest revision as of 11:19, 2 January 2022

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.

Examples

An example of a classic problem is as follows:

"How many numbers less than or equal to 100 are divisible by either 2 or 3?"

Solution: Clearly, there are 50 numbers less than 100 that are divisible by 2 and 33 that are divisible by 3. However, we note that we overcount several numbers, such as 12, which is divisible by both 2 and 3. To correct for this overcounting, we must subtract out the numbers that are divisible by both 2 and 3, as we have counted them twice. A number that is divisible by both 2 and 3 must be divisible by 6, and there are 16 such numbers. Thus, there are $50+33-16=\boxed{67}$ numbers that are divisible by either 2 or 3. (Note that it is not a coincidence that 67 is close to two-thirds of 100! We can approach this problem in a constructive way, building the set based on the remainders when divided by 3, but that is a different subject).

Another basic example is combinations. In these, we correct for overcounting with division, by dividing out what we overcount (as opposed to above where we subtracted it out).

Here is MATHCOUNTS 2008 National Target #1: Try to solve this.

"How many numbers less than or equal to 100 are divisible by 2 or 3 but not 4?".

Now see we have another type of overcounting. For example, we have $n$ people at a party and everyone will handshake with each other. Suppose we are given an order to count the number of handshakes. It's not a matter of a great deal if there are less than 10 persons. But assume a party from the President, there will be millions of people. Now the task seems impossible without mathematics. Suppose we know the total number of people invited to the party, say $n$.

One person will handshake with all others except himself,i.e, he will handshake with $n-1$ people.Now since the total of people in the party is $n$.So there will be $n*(n-1)$ handshakes. Now let's try our formula for two people. According to the formula we get 2 handshakes, but wait, we will have only 1 handshake between two persons. That means we have overcounted somewhere.

Actually, we counted 1 handshake twice for the two persons. In our formula, we have overcounted each handshake twice. One handshake for Person A to Person B and another for Person B to person A.So basically, $2h = n*(n-1) \implies h = \frac{n*(n-1)}{2}$ where h is the number of handshakes. Now our formula tally with our experiment results. (To easily solve a problem, we overcount and then divide with number of times we overcounted)

Here is a question to try:

"How many diagonals does an n-sided polygon have?????" Answer to the question and lots more is given in this (video) Other examples of overcounting are shown in the videos below.

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=169140"