Sample Problem 1. How many positive integers less than 101 are not multiples of 3?
If we start out trying to to directly count this quantity, it quickly becomes apparent that this is fairly hard. We find that it is hard to identify which numbers are not multiples of 3 without initially thinking about which numbers are. Thus, it would make sense to try to think about the problem in a different way.
Instead of trying to count the number of numbers that are not a multiple of three, it will be much simpler to count how many multiples of 3 are below 101 and subtract that from the number of total positive integers below 101. We can easily see that there are 33 positive multiples of 3 below 101 and that there a total of 100 positive integers. Thus, there are a total of 100-33=67 positive integers that are not multiples of 3. The strategy used in this problem of counting the opposite of what you want and subtracting it from the total is a very potent one. This strategy is called complementary counting. It is often good to use complementary counting when counting something directly seems hard, especially if the problem asks explicitly for the number of one thing that is not something else or without a certain attribute.
Instead of trying to count the number of numbers that are not a multiple of three, it will be much simpler to count how many multiples of 3 are below 101 and subtract that from the number of total positive integers below 101. We can easily see that there are 33 positive multiples of 3 below 101 and that there a total of 100 positive integers. Thus, there are a total of 100-33=67 positive integers that are not multiples of 3. The strategy used in this problem of counting the opposite of what you want and subtracting it from the total is a very potent one. This strategy is called complementary counting. It is often good to use complementary counting when counting something directly seems hard, especially if the problem asks explicitly for the number of one thing that is not something else or without a certain attribute.
Sample Problem 2. How many positive integers below 100 are multiples of 3 but not 8?
In this problem it isn't apparent which numbers are multiples of 3 but not multiples of 8. Thus, we think of using complementary counting. It is important to be careful here, because it may at first appear that, when we count the opposite, we count the multiples of 8 but not 3. However, we instead need to count the number of positive integers less than 100 that are not multiples of 3 or are multiples of 3 and 8. Thus, it is important to be careful in making sure we count all numbers not in our desired set but in our total and to make sure that we properly determine what opposite to count. Using complementary counting to solve the problem in this way is perfectly legitimate, but we will show another way here for the purpose of introducing a useful concept.
Instead of trying to use positive integers below 100 as the total, we will instead think of a different total. We will use the multiples of 3 below 100, because then we essentially reduce our problem to the previous one. There are 33 multiples of 3 below 100. Next, we need to remove the numbers of multiples of 3 that are also a multiple of 8. We can easily see that each such number will be a multiple of 24. We can easily count that there are 4 positive multiples of 24 below 100. Thus, there are 33-4=29 positive integers meeting the desired conditions.
Instead of trying to use positive integers below 100 as the total, we will instead think of a different total. We will use the multiples of 3 below 100, because then we essentially reduce our problem to the previous one. There are 33 multiples of 3 below 100. Next, we need to remove the numbers of multiples of 3 that are also a multiple of 8. We can easily see that each such number will be a multiple of 24. We can easily count that there are 4 positive multiples of 24 below 100. Thus, there are 33-4=29 positive integers meeting the desired conditions.
Exercises
- How many ways can 5 beads, 2 blue and 3 red, be arranged in a line without the blue beads being next to each other (beads of the same color are indistinguishable)?
Solution 1
We will count this quantity by taking the total number of arrangements and subtracting the arrangements with two blue beads in a row. There are a total of \(\binom{5}{2}=10\) arrangements and a total of 4 ways to arrange the beads with the 2 blue beads next to each other. Thus, there are 6 arrangements fitting the desired constraints.