Sample Problem 1. In a school, there are 20 student who play sports, 15 who play musical instruments, and 5 who play a sport and a musical instrument. How many students play a sport or a musical instrument (or both)?
When doing this problem, we need to be careful to not over count any student. For example, answers of 15+20=35 or 15+20+5=40 would both be wrong because they over count the number of students doing both. If you are confused in questions like these, especially when they get more complicated, it can often be a good idea to draw a Venn Diagram like the one seen below.
By drawing a Venn Diagram, we can make sure to not over count any person. Once we have drawn the Venn Diagram, as in the picture above, we can often easily find the desired value. In this case, it is the total number of students, so we just add up the numbers in the diagram to get a total of 30 students.
Drawing a Venn Diagram certainly works and is a good technique to remember when you're confused, but it also isn't the most efficient. We would prefer if there were an algebraic way to solve this problem without drawing out a diagram. Thus, we will try to look at exactly what we did in drawing the Venn Diagram in order to find an algebraic representation of our steps. In drawing this diagram, we were initially given 20 students who play sports and 15 students who play a musical instrument. We subtracted the 5 people doing both activities from the 20 people playing sports and the 15 people playing an instrument in order to find the people doing just one activity. We then added the 5 people back in to account for the people doing both activities. Thus, we subtracted 5 twice and added it once, for a total of subtracting it once.
The process described above can be easily generalized to see that the total number of elements that are in either one set or another (or both) is equal to the sum of the number of elements in each set individually minus the number of elements that are in both sets.
Drawing a Venn Diagram certainly works and is a good technique to remember when you're confused, but it also isn't the most efficient. We would prefer if there were an algebraic way to solve this problem without drawing out a diagram. Thus, we will try to look at exactly what we did in drawing the Venn Diagram in order to find an algebraic representation of our steps. In drawing this diagram, we were initially given 20 students who play sports and 15 students who play a musical instrument. We subtracted the 5 people doing both activities from the 20 people playing sports and the 15 people playing an instrument in order to find the people doing just one activity. We then added the 5 people back in to account for the people doing both activities. Thus, we subtracted 5 twice and added it once, for a total of subtracting it once.
The process described above can be easily generalized to see that the total number of elements that are in either one set or another (or both) is equal to the sum of the number of elements in each set individually minus the number of elements that are in both sets.
Sample Problem 2. Generalize the last problem in order to find a general formula for the total number of elements in any of n sets. Make sure to not over count any elements. You are given the total number of elements in the intersection of any z sets for each z less than or equal to n.
It isn't immediately apparent where to start, so we will begin by looking at another example. We will look at three different sets and try to find a general formula for that case. First of all, if we just add together the number of elements in each set, we will have counted the elements in the intersection between exactly two sets twice (once for each set they are in). Thus, we need to subtract the number of elements in each pair of two different sets. Next, for the elements in all 3 sets, we counted them 3 times when we added the elements in each individual set, and we subtracted them \(\binom{3}{2}=3\) times when we subtracted each element in two sets (once for each combination of two sets from the 3 sets the element is in). Thus, we must add in the number of elements in 3 sets.
From the two previous examples, we may start to see a pattern emerge. It would appear that we start by adding in the number of elements in each set, then subtract the number of elements in each pair of sets, add the number of elements in each triplet of sets, subtract the number of elements in each group 4 sets, and so on, alternating adding and subtracting until we get to the elements in all n sets.
We will prove that the above method works by proving that any arbitrary element in exactly \(g\) sets will be counted exactly once, similar to how we worked out the total number of elements in at least one set for 3 total sets. It can easily be verified that, for any element in exactly \(g\) sets , we add or subtract it \(\binom{n}{s}\) times when we add or subtract the elements in each group of \(s\) sets. Thus, any element in exactly \(g\) sets will be counted \[\binom{g}{1}-\binom{g}{2}+\binom{g}{3}-\binom{g}{4}- \ldots \pm\binom{g}{g}\], where the sign of the last binomial coefficient depends on the parity (even or odd) of \(g\). However, note that \[\binom{g}{0}-(\binom{g}{1}-\binom{g}{2}+\binom{g}{3}-\binom{g}{4}- \ldots \pm\binom{g}{g})=(1-1)^g=0\] (this is because of the Binomial Theorem, which we will prove in the Pascal's Triangle lesson). However, note that this would imply \[\binom{g}{1}-\binom{g}{2}+\binom{g}{3}-\binom{g}{4}- \ldots \pm\binom{g}{g}=\binom{g}{0}=1\], or that we counted this element exactly once as desired.
While this general formula is good to know and will be useful, it is even more important to be able to understand the derivation of the formula so that you would know how to find the number of elements in at least \(h\) of the \(n\) total sets. Also, remember that if you are ever stuck on a problem of this type, using a Venn Diagram is always an option, even if it takes a bit longer.
From the two previous examples, we may start to see a pattern emerge. It would appear that we start by adding in the number of elements in each set, then subtract the number of elements in each pair of sets, add the number of elements in each triplet of sets, subtract the number of elements in each group 4 sets, and so on, alternating adding and subtracting until we get to the elements in all n sets.
We will prove that the above method works by proving that any arbitrary element in exactly \(g\) sets will be counted exactly once, similar to how we worked out the total number of elements in at least one set for 3 total sets. It can easily be verified that, for any element in exactly \(g\) sets , we add or subtract it \(\binom{n}{s}\) times when we add or subtract the elements in each group of \(s\) sets. Thus, any element in exactly \(g\) sets will be counted \[\binom{g}{1}-\binom{g}{2}+\binom{g}{3}-\binom{g}{4}- \ldots \pm\binom{g}{g}\], where the sign of the last binomial coefficient depends on the parity (even or odd) of \(g\). However, note that \[\binom{g}{0}-(\binom{g}{1}-\binom{g}{2}+\binom{g}{3}-\binom{g}{4}- \ldots \pm\binom{g}{g})=(1-1)^g=0\] (this is because of the Binomial Theorem, which we will prove in the Pascal's Triangle lesson). However, note that this would imply \[\binom{g}{1}-\binom{g}{2}+\binom{g}{3}-\binom{g}{4}- \ldots \pm\binom{g}{g}=\binom{g}{0}=1\], or that we counted this element exactly once as desired.
While this general formula is good to know and will be useful, it is even more important to be able to understand the derivation of the formula so that you would know how to find the number of elements in at least \(h\) of the \(n\) total sets. Also, remember that if you are ever stuck on a problem of this type, using a Venn Diagram is always an option, even if it takes a bit longer.
Exercises
- At Math Problem High School, students either play bridge, are on the math team, play chess, or are on the science team. If \(a\) students play bridge, chess, and are on the math team; \(b\) students play bridge and chess and are on the science team; \(c\) students play bridge and are on the math and science teams; \(d\) students play chess and are on the math and science teams; and \(e\) students play bridge and chess and are on the math and science teams, how many students are on at least 3 of the 4 teams?
- How many positive integers below 101 are not multiples of 3 or 8?
Solution 1
We will solve this problem just as we solved the previous ones. If we add together the number of students in each group of 3 teams we will have counted the students in all 4 teams \(\binom{4}{3}=4\) times, so we need to subtract the number of students that are in all 4 teams 3 times. Thus, we get that the total number of people in at least 3 clubs to be \(a+b+c+d-3e\).
Solution 2
We will use complementary counting. First, we will count the numbers of multiples of 3 or 8 below 101. We can easily see that there are 33 multiples of 3, 12 multiples of 8, and 4 multiples of 3 and 8. Thus, there are 33+12-4=41 multiples of 3 or 8 below 101 and 100-41=59 positive integers that are not multiples of 3 or 8 below 101.