4
$\begingroup$

Let $X=\{1,2,3,\ldots,10\}$. Find the number of pairs $\{A,B\}$ Such that $A,B\subseteq X$, $A\neq B$ and $A \cap B=\{5,7,8\}$.

Not a homework question. It is a question from a Math olympiad.

3 Answers 3

6

The problem is equivalent to choosing two non-intersecting subsets of $\{1,2,3,4,6,9,10\}$ such that at least one of them is non-empty, and adding $\{5,7,8\}$ to each. Which, in turn, is equivalent to splitting the elements of $\{1,2,3,4,6,9,10\}$ into three sets ('give' each number a sign - whether it goes to $A$, to $B$ or nowhere) such that at least one of the first two is non-empty.
There are $3^7$ options to split those elements into three sets ($3$ options for every elememt to go to). In one of those options, the first two will be empty.
Hence you have $3^7-1=2186$ options to choose $(A,B)$.
If you want to find the number of options for $\{A,B\}$ - divide by $2$, i.e. $\frac12\left(3^7-1\right)=1093$

  • 0
    Nice explanation.2015-03-12
0

Basically you are searching for $A',B'\subseteq X':=\{1,2,3,4,6,9,10\}$.

Let $A'$ have $k$ elements. There are ${7\choose k}$ such sets $A'$. The number of corresponding sets $B'$ is equal to $2^{7-k}$ (because $B'$ is any subset of $X'\setminus A'$.

Now we have to sum up over all $k$, $0\leq k\leq7$, and remove the case $A'=B'=\emptyset$:

$-1+\sum_{k=0}^7 {7\choose k} 2^{7-k}=2186.$

And as Dennis Gulko points out in his answer, you want to get only one half of this number, i.e. $1093$.

0

There are only 7 more elements to place in $A$ or $B$. To meet the intersection criteria, every extra element may only: go into $A$, or go into $B$, or go into neither. Le's call "neither" the third set. So you've got $3$ choices for each of the extra elements, which is $3^7$. However, we've counted $A=B=\{5,7,8\}$, so the correct answer is $3^7-1$.

  • 0
    Almost exact duplicate of @DennisGulko's answer, but I'd still like to show the third set via natural language.2012-12-02