Taking the right approach is the key to most GMAT and GRE quant problems, and combinatorics problems are no different. Almost all combinatorics problems can be solved with a single tool that can be used in two different ways – one way when order matters, and another way when order doesn’t matter. However sometime it pays to take a different approach.
How many integers less than 1000 are divisible by neither 3, 5, nor 7?
(A) 457 (B) 507 (C) 534 (D) 543 (E) 684
Translation
First, we can change things around a bit – let’s find all the numbers that ARE divisible by 3, 5, or 7, and then subtract that number from 1000. We have to careful about integers that are divisible by more than one of our numbers. For example, 21 is divisible by 3 and 7, but we can only count it once. This trick or trap comes up a lot in combinatorics problems. It’s called “double counting.”
To avoid this problem we can use Venn diagrams. Since we have three sets – numbers divisible by 3, numbers divisible by 5, and numbers divisible by 7 – we need a three-circle Venn diagram like this:
I like to draw these diagrams inside a box so I don’t forget about things that might be floating around outside my sets. This is very important for this problem because the final step will be subtracting the value we get from the total number of elements.
Let’s agree the circle labeled A represents all the numbers less than 1000 which are divisible by 3. The circle labeled B represents all the numbers less than 1000 which are divisible by 5. Finally, the circle labeled C will be all the numbers which are divisible by 7.
Solution
When working with three-set Venn diagrams it’s best to start from the inside and work your way out. All three circles intersect in the center:
This part of the diagram represents the numbers that are divisible by 3, 5 and 7. If a number is divisible by 3, 5, and 7, it will also be divisible by their least common multiple. Because 3, 5, and 7 don’t share any factors, their least common multiple is the product of 3, 5, and 7: 105. To find the number of multiples of 105 less than 1000, we divide 1000 by 105. Note that we only want the integer part so we’re going to ignore the remainder.
The number of elements in A and B and C = the integer part of (1000/105) = 9
Now we continue to work our way out by looking at the portions of the diagram where two of the three sets overlap:
(1) MULTIPLES OF 3 AND 5
(2) MULTIPLES OF 5 AND 7
(3) MULTIPLES OF 3 AND 7
Since we’ve already counted the multiples in the center (the blue part of the diagram) we need to be careful not to count them twice and only find the elements in the red parts of the diagram.
Let’s move from top to bottom:
MULTIPLES OF 3 AND 5: Multiples of 3 and 5 are multiples of 15
The number of elements in A and B but not C = the integer part of (1000/15) – 9 = 66 – 9 = 57
MULTIPLES OF 5 AND 7: Multiples of 5 and 7 are multiples of 35
The number of elements in A and C but not B = the integer part of (1000/35) – 9 = 28 – 9 = 19
MULTIPLES OF 3 AND 7: Multiples of 3 and 5 are multiples of 15
The number of elements in B and C but not A = the integer part of (1000/21) – 9 = 47 – 9 = 38
Now our diagram looks like this:
Almost there… remember not to double count the portions of the diagram that are already labeled!
MULTIPLES OF 3 AND NOT 5 OR 7:
The number of elements in A but not in C or B = the integer part of (1000/3) – (9 + 19 + 57) = 333 – 85 = 248
MULTIPLES OF 5 AND NOT 3 OR 7:
The number of elements in B but not in A or C = the integer part of (1000/5) – (9 + 38 + 57) = 200 – 104 = 96
MULTIPLES OF 7 AND NOT 3 OR 5:
The number of elements in C but not in A or B = the integer part of (1000/7) – (9 + 19 + 38) = 142 – 66 = 76
Our final diagram:
So the number of elements less than 1000 which are divisible by 3, 5 or 7 =
248 + 96 + 76 + 19 + 57 + 38 + 9 = 543
And the number of elements less than 1000 which are NOT divisible by 3, 5, nor 7 =
1000 – 543 = 457
The answer is (A).
Keep in mind
- This is not the end of the story with Venn diagrams
- There are multiple ways to solve any GMAT problem and that’s true here as well
- This is simply an illustration of how to use a Venn diagrams
800 Challenge
I’m going to leave you with some challenging problems to try on your own. All of these problems can be solved with Venn diagrams
1. How many positive integers less than 1,000,000 are neither squares nor cubes?
2. Given a random 6-digit integer, what is the probability that the product of the first and last digit is even?
Answers: 1. 998,910 2. 13/18 or approximately 72%