# Let $X=\{1,2,3,\ldots,10\}$ Find the number of pairs $\{A,B\}$

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.

-
Thanks a TON Dennis!!! – Saurabh Raje Dec 2 '12 at 15:17

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$

-
$3^7=2187{}{}$. – yo' Dec 2 '12 at 14:02
@tohecz: thanks. Never been good in arithmetic ;) – Dennis Gulko Dec 2 '12 at 14:04
(+1) Exactly the same as the three-boxes approach I came upon. @tohecz avoid $A=B=\{5,7,8\}$, so subtract one. – FrenzY DT. Dec 2 '12 at 14:04
@FrenzYDT. I know. There was a math typo, see the edit history. – yo' Dec 2 '12 at 14:06
@DennisGulko How did you get 3^7? and, why one half of the combinations? – Saurabh Raje Dec 2 '12 at 15:22

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

-

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

-
Almost exact duplicate of @DennisGulko's answer, but I'd still like to show the third set via natural language. – FrenzY DT. Dec 2 '12 at 14:14