Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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$

share|cite|improve this answer
$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 Li 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$.

share|cite|improve this answer

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

share|cite|improve this answer
Almost exact duplicate of @DennisGulko's answer, but I'd still like to show the third set via natural language. – Frenzy Li Dec 2 '12 at 14:14

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.