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
    $3^7=2187{}{}$.2012-12-02
  • 0
    @tohecz: thanks. Never been good in arithmetic ;)2012-12-02
  • 0
    (+1) Exactly the same as the three-boxes approach I came upon. @tohecz avoid $A=B=\{5,7,8\}$, so subtract one.2012-12-02
  • 0
    @FrenzYDT. I know. There was a math typo, see the edit history.2012-12-02
  • 0
    @DennisGulko How did you get 3^7? and, why one half of the combinations?2012-12-02
  • 0
    $3^7$ since there are $7$ elements remaining and $3$ options for each (in $A$, in $B$, not in $A\cup B$). Hence we have: $3\times 3\times\cdots\times 3=3^7$. Half because you wanted un-ordered pair, i.e $A=\{5,7,8\}$ and $B=\{5,7,8,9\}$ or $A=\{5,7,8,9\}$ and $B=\{5,7,8\}$ are counted as one option.2012-12-02
  • 0
    Which concept or formula is it that tells you that when you have x elements, and y options for each, no. of combinations are $y^x$ ??2012-12-03
  • 0
    That's called the rule of product -en.m.wikipedia.org/wiki/Rule_of_product2012-12-03
  • 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