Sets A, B With 2 and 4 Elements — Subsets of A×B With 3+ Elements

JEE Main 2015. Previous Year Question.

Problem

Let $A$ and $B$ be two sets containing $2$ elements and $4$ elements respectively. The number of subsets of $A\times B$ having $3$ or more elements is:

Key insight. $A\times B$ is just a set with $2\times4=8$ elements — the fact that it’s a Cartesian product doesn’t matter once its size is known. Counting subsets with “3 or more” elements directly would mean adding up $\binom{8}{3}+\binom{8}{4}+\cdots+\binom{8}{8}$, but it’s far quicker to subtract the few small subsets (sizes $0$, $1$, $2$) from the total.

Watch this explained step by step →  ·  More on the Shiwam’s Classes channel

Approach

Find the total number of elements in $A\times B$, then the total number of subsets of a set that size. Subtract the number of subsets with $0$, $1$, or $2$ elements (which is quick to compute directly) to leave only those with $3$ or more elements.

Solution

Step 1 — Find the size of A × B

$$|A\times B| = |A|\times|B| = 2\times4 = 8$$

Step 2 — Find the total number of subsets

A set with $8$ elements has $2^8=256$ subsets in total.

Step 3 — Count subsets with fewer than 3 elements

$$\binom{8}{0}+\binom{8}{1}+\binom{8}{2} = 1+8+28 = 37$$

Step 4 — Subtract to get subsets with 3 or more elements

$$256-37 = 219$$

Answer

Common mistakes

• Trying to directly sum $\binom{8}{3}+\binom{8}{4}+\cdots+\binom{8}{8}$. This gives the same correct answer but takes far more calculation than the complement approach, which only needs three small binomial coefficients.
• Forgetting the empty set counts as a valid subset with $0$ elements. Skipping $\binom{8}{0}=1$ in the subtraction changes the final count by one.

Practise next

• Let $P$ and $Q$ be sets with $3$ and $5$ elements respectively. Find the number of subsets of $P\times Q$ having $4$ or more elements, using the same complement-counting method.