Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
    
Thanks a TON Dennis!!! –  Saurabh Raje Dec 2 '12 at 15:17
    
@Dimension10 The [homework] tag specifically asks users not the add it to the posts of others unless it is homework. I understand your point that this is almost homework, but the [contest-math] tag is more appropriate. –  user1729 Jul 15 '13 at 10:27
add comment

3 Answers 3

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|improve this answer
    
$3^7=2187{}{}$. –  tohecz 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. –  tohecz 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
show 3 more comments

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|improve this answer
add comment

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|improve this answer
    
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
add comment

Your Answer

 
discard

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.