Intersection Requirement
How many ordered pairs ( A , B ) , where A , B are subsets of { 1 , 2 , 3 , 4 , 5 } are there, such that ∣ A ∩ B ∣ = 1 ?
Details and assumptions
Students who are unfamiliar with Set Notation can refer to the blog post on Set Notation for definitions.
The answer is 405.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
4 solutions
Let us assume that A ∩ B = 1 . Note that 2 , 3 , 4 , 5 can either be ∈ A , ∈ B , or not in either. Therefore, there are 3 × 3 × 3 × 3 = 8 1 possible choices.
Since A ∩ B can equal 1 → 5 , we multiply by 5 to get a final answer of 8 1 × 5 = 4 0 5 and we are done.
This answer is somewhat complex but produced the same result, we are going to consider the set A:
1) A has only 1 element: the 1 element of A can have 1 choice, and B has the same element and possibly 0, 1, 2, 3 or 4 of the remaining elements, which is calculated as ( 0 4 ) + ( 1 4 ) + ( 2 4 ) + ( 3 4 ) + ( 4 4 ) = 1 + 4 + 6 + 4 + 1 = 5*16 = 80
2) A has 2 elements: the 2 elements of A are chosen in 5C2 ways, and B should contain either the first or the second term in A, plus 0, 1, 2 or 3 elements from the remaining, giving ( 2 5 ) * 2 * ( ( 0 3 ) + ( 1 3 ) + ( 2 3 ) + ( 3 3 ) ) = 160
3) A has 3 elements: A's choices are 5C3, and B has one of the three choices for the same element, plus 0, 1 or 2 from the remaining elements, giving ( 3 5 ) * 3 * ( ( 0 2 ) + ( 1 2 ) + ( 2 2 ) ) = 3*4 = 120
4) A has 4 elements: A's choices are 5C4, and B has one of the four choices for the same element, plus 0 or 1 from the remaining elements, giving ( 4 5 ) * 4 * ( ( 0 1 ) + ( 1 1 ) ) = 40
5) A has 5 elements: A's choices are 5C5, and B has one of the five choices for the same element, plus 0 elements, giving ( 5 5 ) * 5 * ( ( 0 0 ) ) = 5
Adding all these terms: 80 + 160 + 120 + 40 + 5 = 4 0 5
I did a similar method.
We are looking for pairs of subsets whose intersection is a set of cardinality 1. In other words, we are looking for pairs of subsets with only one common elements.
Here we identify five cases.
A has one element, which can be chosen in 5C1 number of ways. B must contain the element in a A (1C1), plus any subset of the additional 4 unchosen elements (2^4). So we have 5C1 1C1 2^4.
OR A has two elements, which can be chosen in 5C2 number of ways. B must contain 1 of those 2 elements (2C1), plus any subset of the additional 3 unchosen elements, (2^3). So we have 5C2 2C1 2^3
OR A has three elements, which can be chosen in 5C3 number of ways. B must contain 1 of those 3 elements (3C1), plus any subset of the additional 2 unchosen elements, (2^2). So we have 5C3 3C1 2^2.
OR A has four elements, which can be chosen in 5C4 number of ways. B must contain 1 of those 4 elements (4C1), plus any subset of the additional 1 unchosen element, (2^1). So we have 5C4 4C1 2^1.
OR A has five elements, which can be chosen in 5C5 number of ways. B must contain 1 of those 5 elements (5C1), plus any subset of the additional 1 unchosen element (in this case there are no unchosen elements). 5C5 5C1 2^0.
We add together the results from each case, for a total of 405.
We can choose the element in common : there are 5 ways to do this.
Then the other elements have got 3 different possibilities : either they ∈ A , ∈ B or they belong to neither.
Hence there are 5 ∗ 3 4 = 4 0 5 ordered pairs.
There are 5 ways to choose which element is in the intersection, and for the other 4 elements, they can either go in A , B , or in neither, which is 3 4 possibilities. The answer is 5 ⋅ 3 4 = 4 0 5 .