April 2010: Problem and Solution
Problem of the Month - April 2010: Subsets
In this problem we examine the number of subsets a given set might have. The set
A is said to be a subset of the set B if all elements of A
are elements of B. Another way to think of this is to think of one set as
being "contained" by another, or "included" in the greater set. Similarly, a superset
of a given set is one which "includes" all elements of its respective subset. For
example, the set {1,2} is a subset of of the set {1,2,3}. By notation, a proper subset
of a set B is one that is a subset of B but is not equal to B.
Also, note that the null (empty) set, denoted { }, is a subset of all sets except
itself.
- Determine the number of distinct subsets of the set {0,1,2} (remember the empty
set!).
- Determine the number of distinct subsets of a set with n distinct elements.
- How many subsets of {{1,2},{1,3},{1,4},{2,3},{2,4},{3,4}} satisfy the property that
the union of each of the elements of the set forms the set {1,2,3,4}?
April 2010: Solution
To determine the number of distinct subsets of a set with n distinct elements,
consider each of the n elements. This element can either be in a subset,
or not in the subset; thus, there are two different classes of sets with respect
to this one element. Furthermore, every such subset can be defined by whether each
of the n elements is in or out of the set, so we know that there are a total
of 2n distinct subsets. In the case of the subset {0,1,2}, for
example, there are 23=8 subsets.
From the paragraph above, we see that there are 64 subsets of the set, {{1,2},{1,3},{1,4},{2,3},{2,4},{3,4}}.
By counting the number of subsets whose union is not {1,2,3,4}, we can determine
our desired value.
- If the union of the sets is "missing" one value, then the three sets that include
that value must not be part of the subset; for example, the set, {{1,2},{1,3},{2,3}},
is missing each of the elements that contain the value "4." Furthermore, the subset
could be missing at most one of the remaining 3 sets; for example, {{1,2},{1,3}}.
Since there are four values to choose in the first step and three sets to choose
in the second, there are 4*3=12 total subsets in this case.
- The set could also be "missing" two values, in which case it is fairly clear that
there is a unique set that corresponds to the two chosen values; for example, if
the set is "missing" values 2 and 4, the set in question must be {{1,3}}. There
are 4C2=6 ways to choose the two missing elements.
- Finally, the set can be "missing" all four elements; that is, the set in question
is the null set.
Adding together all of these cases, there are 12+6+1=19 ways that the union of the
elements of the subset does not equal {1,2,3,4}; thus, there are 64-19=45
sets that do have the desired property.
« Back to Problems