Permutations & Combinations
Ordered pairs from set S with size and intersection constraints
MJAT_TS5_P2
Grade 12
Question:
Let $S=\{1,2,3,4,\ldots,10\}$ and $A,B\subseteq S$. The number of ordered pairs $(A,B)$ satisfying: (i) $n(A)\leq n(B)$; (ii) $n(A\cap B)=4$; (iii) $A\cup B=S$ equals $k$. The maximum digit in $k$ is:
Step-by-Step Solution
Key Concept: Since $A\cup B=S$ and $|A\cap B|=4$: $|A|+|B|-4=10\Rightarrow|A|+|B|=14$. The 4 elements in $A\cap B$ can be chosen in $\binom{10}{4}$ ways. The remaining 6 elements are split between $A\setminus B$ and $B\setminus A$. With $|A\cap B|=4$: $|A|=4+|A\setminus B|$ and $|B|=4+|B\setminus A|$. Condition $|A|\leq|B|$: $|A\setminus B|\leq|B\setminus A|$.
$k=8820$, max digit $=\mathbf{8}$.
Correct Answer: 8