Too Many Daughters.

Algebra Level 2

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.)

2928 2927 2925 2929 2926

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.

1 solution

Chris Lewis
May 21, 2019

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 6 independent "CD" branches (grand-daughter/great-grand-daughter pairs) of the family tree:

From each of these 6 6 branches, we can pick either C, D, or no-one, giving 3 3 valid choices. Hence there are 3 6 = 729 3^6=729 such subsets.

Now let's consider the subsets that don't contain Alice. Again, we can divide the tree, this time into 3 3 "BCD" branches; one of these is shown below:

If the subset doesn't contain Bea, we have 2 2 independent "CD" branches, each with 3 3 valid options (the same as the case above containing Alice), for a total of 3 2 = 9 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 4 valid subsets containing Bea.

So each of the 3 3 independent branches leads to 9 + 4 = 13 9+4=13 subsets, for a total of 1 3 3 = 2197 13^3=2197 .

In total, then, there are 729 + 2197 = 2926 729+2197=\boxed{2926} 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 6 and 3 3 of these. This means the answer has the form x 6 + y 3 x^6+y^3 for some non-negative integers x x and y y , and it's trivial to check that only one of the answer options works.

Thank you. Nice and clear solution. The idea of the names is helpful too,

Hana Wehbi - 2 years ago

Log in to reply

Thanks! Feels a bit clunky to do case analysis, though - by the time we're down to Zelda, Zoe and Zara this approach would be horrific. Do you know of any other way?

Chris Lewis - 2 years ago

Actually, I solved it the same way. Trees are the best here to show subsets. How did you do your tree diagrams, what software or system did you use.

Hana Wehbi - 2 years ago

Log in to reply

I used SmartArt on Excel, then tinkered with the formatting. I'm sure there are better options out there!

Chris Lewis - 2 years ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...