$4$-element subset of $\{1..6\}$ that includes $1$ or $4$, and $2$ or $5$, and $3$ or $6$?

Question

I am stuck on the following question which was asked in our combinatorics exam:

Let us consider the set $S=\{1,2,3,4,5,6\}$. We want to find a set $A\subset S$ such that $A$ must have the following property:

• either $1$ or $4$ must belong to $A$.
• either $2$ or $5$ must belong to $A$.
• either $3$ or $6$ must belong to $A$.

Also $A$ must have $4$ elements in it.

What are the possible ways to form the set $A$?

My try:

For the 1st element of $A$ we have $2$ choices namely $1,4$, for second we have $2$ choices namely $2,5$ and for $3rd$ element we have $2$ choices namely $3,6$. Thus there are in total $2\times 2\times 2=8$ choices for the first 3 elements of $A$.

Now for the 4th element we have $3$ choices. So there will be $\binom{3}{1}=3$ choices.

So the total ways of forming $A$ is $8\times 3=24$ .

There was also a 2nd question which asked what if $A$ had $5$ or $6$ elements?

If $A$ had $5$ elements I answered that there will be $8\times \binom{3}{2}=24$ choices.

Now if $A$ had $6$ elements I answered that there will be $8\times \binom{3}{3}=8$ choices.

My both answers had gone wrong.Can someone please help me figure it out. I dont understand why my answer is wrong and how can I get the correct answer.

Is it possible for someone to please help me out?

Answer 1

It is never a good idea to start by fulfilling the condition and then letting the rest of the elements do whatever they want. You overcounting part of the results in this way. For example, the set $\{1,2,3,4\}$ is counted twice -- once when $1$ was selected in step 1 and once when it was $4$.

The correct answer will be to determine which couple is entirely in $A$. You have 3 ways to choose this couple, then 2 ways to choose a representative from each of the other couples. In total: $3\times 2 \times 2=12$.

Similarly, if $A$ had to have 5 elements, you need to choose which couple is not represented, then choose one element of this couple (and the 2 others come in completely). Total: $3\times 2=6$.

If $A$ to have 6 elements, there is one option.

Answer 2

As pointed out by YJT you are overcounting the subsets.

This is another approach. There are $\binom{6}{4}=15$ subsets of $4$ elements out of $6$. Among them there is just one subset which contradicts the first property, i.e. it does not contain both $1$ and $4$, namely $\{2,3,5,6\}$. Similarly for the couples $2$, $5$ and $3$, $6$. Since the excluded sets are distinct, it follows that the number of possible ways to form the set $A$ is $$15-1-1-1=12.$$

If $A$ had to have $5$ or $6$ elements it is even easier because there are no subsets to exclude. Hence the answers are $\binom{6}{5}=6$ and $\binom{6}{6}=1$ respectively.

Answer 3

You have to choose one full pair from $\{1,4\}$, $\{2,5\}$, $\{3,6\}$, and one element from each of the two other pairs. The full pair can be selected in $3$ ways, and then the remaining elements in $2\cdot2$ ways; makes $12$ in all.