Alice has three daughters, each of whom has two daughters; each of Alice’s six grand- daughters has one daughter. How many sets of women from the family of 16 can be chosen such that no woman and her daughter are both in the set?
(Include the empty set as a possible set.)
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.
Here's the female side of Alice's family tree:
What helpful names they have! Let's consider the valid subsets that contain Alice. None of her daughters can be in such a subset, and we're left with 6 independent "CD" branches (grand-daughter/great-grand-daughter pairs) of the family tree:
From each of these 6 branches, we can pick either C, D, or no-one, giving 3 valid choices. Hence there are 3 6 = 7 2 9 such subsets.
Now let's consider the subsets that don't contain Alice. Again, we can divide the tree, this time into 3 "BCD" branches; one of these is shown below:
If the subset doesn't contain Bea, we have 2 independent "CD" branches, each with 3 valid options (the same as the case above containing Alice), for a total of 3 2 = 9 valid subsets.
If the subset does contain Bea, it can't contain either of her daughters, but can contain any or none of her two grand-daughters; so there are 4 valid subsets containing Bea.
So each of the 3 independent branches leads to 9 + 4 = 1 3 subsets, for a total of 1 3 3 = 2 1 9 7 .
In total, then, there are 7 2 9 + 2 1 9 7 = 2 9 2 6 valid subsets.
There is a shortcut in this question, given the answer options. We only need to go as far as working out the numbers of branches in the two cases "Alice is in the subset" and "Alice is not in the subset". As is clear from the family tree, there are (respectively) 6 and 3 of these. This means the answer has the form x 6 + y 3 for some non-negative integers x and y , and it's trivial to check that only one of the answer options works.