Let $X=\{1,2,3,...,10\}$. Find the number of pairs of $\{A,B\}$ such that $A\subseteq X, B\subseteq X, A\ne B$ and $A\cap B=\{2,3,5,7\}$.
Problem
Source: CRMO 2012 Region 1 p4
Tags: Subsets, combinatorics, Combinatorics of set
11.08.2020 07:03
answer should be $2^6.2^6=2^{12}$
11.08.2020 20:35
First we notice that if $\{A,B\}$ is a solution then so is $\{B,A\}$.Thus we shall calculate $W.L.O.G.$ when $card(A) \leq card(B)$. Now we shall divide a little bit into cases: 1.Case $A=\left\{2,3,5,7\right\}$ Since $card(A)=4$, then by the condition $A \cap B$, $card(B) \geq 4$, and since $A \neq B$, we have that $card(B) > 4$. Now we are going to have to calculate the number of solutions for $B$.This is easily done since the number is: $$\sum_{k=1}^{6} {6 \choose k} = 2^6 - 1$$ 2.Case $A=\left\{a,2,3,5,7\right\}$, where $a \in \{1,4,6,8,9,10\}$ Counting in the condition $A \neq B$ we get that the number of solutions for $B$ in this case is (when $a$ is fixed): $$\sum_{k=1}^{5} {5 \choose k} = 2^5-1$$and since we can choose $6$ elements for $a$ we get that the total number of solutions here is: $${6 \choose 1}(2^5-1)$$ After this I started seeing a pattern in the number of solutions here thus I got that the total number for $B$ ( and when $card(A) \geq card(B)$) is: $$2 \sum_{k=0}^{6} {6\choose k}(2^{6-k}-1)$$
12.08.2021 08:52
You all are wrong actual answer is $3^6-1$
11.01.2022 18:31
Hello this is mine solution : we have to place the elements of the set (1,4,6,8,9,10) now each of these 6 elements has 3 choice (either go to A,B or neither A,B) this operation can be done in 3^6 ways but one case arises when all elements neither go in A,B thus total "useful cases" = 3^{6} - 1 ways
16.09.2024 17:44
21.09.2024 08:49
We give both the sets $\{2,3,5,7\}$. Now we have to distribute the rest. Each element has $3$ choices, (a) To go to $A$. (b) To go to $B$. (c) To go to none. Thus $3$ choices for every number. Since there are $6$ of them the answer is $3^6$. But note there is a case where all go to "none". Thus the final answer is $$\boxed{3^6-1}.$$[NOTE: Here "go" is just personifying the elements of the set.]