Difference between revisions of "Overcounting"

(Examples)
Line 3: Line 3:
 
The [[Principle of Inclusion-Exclusion]] (PIE) is a systematic method of repeated overcounting that is a tool in solving many [[combinatorics]] problems.
 
The [[Principle of Inclusion-Exclusion]] (PIE) is a systematic method of repeated overcounting that is a tool in solving many [[combinatorics]] problems.
  
 +
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 <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).
 +
 +
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?".
 
== Examples ==
 
== Examples ==
  

Revision as of 19:42, 1 May 2011

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

The Principle of Inclusion-Exclusion (PIE) is a systematic method of repeated overcounting that is a tool in solving many combinatorics problems.

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 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).

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?".

Examples

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

Invalid username
Login to AoPS