RankRizz
JEE MAIN 2015 · 04 APR OFFLINE+4 / −1MEDIUMTRANSCRIBED

JEE Main 2015 Mathematics question — Cartesian products and counting relations

Let AA and BB be two sets containing four and two elements respectively. Then the number of subsets of the set A×BA \times B, each having at least three elements is

SOLUTION

We have two finite sets, namely AA and BB, whose cardinalities are given to be ∣A∣=4|A| = 4 and ∣B∣=2|B| = 2 respectively.

First, recall the definition of the Cartesian product of two sets.

For any sets XX and YY, the Cartesian product X×YX \times Y is defined as {(x,y)∣x∈X, y∈Y}\{(x,y) \mid x \in X,\, y \in Y\}.

The number of ordered pairs in X×YX \times Y is obtained by the fundamental principle of counting: every element of XX can be paired with every element of YY, so the total number of pairs is the product ∣X∣⋅∣Y∣|X| \cdot |Y|.

Applying this to AA and BB, we obtain

∣A×B∣=∣A∣×∣B∣=4×2=8.|A \times B| = |A| \times |B| = 4 \times 2 = 8.

Thus there are exactly 88 distinct ordered pairs in A×BA \times B. Consequently, A×BA \times B is a set with eight elements.

Next, we are asked to count the subsets of A×BA \times B that have at least three elements.

For a set with nn elements, the total number of all possible subsets (including the empty set) is given by the power set formula 2n2^{n}.

Here, since n=8n = 8, the total number of all subsets of A×BA \times B is

28=256.2^{8} = 256.

However, this total counts subsets of every possible size, from 00 up to 88. We do not want every subset; we only want those subsets whose size (cardinality) is at least 33. Hence we must subtract the numbers of subsets that have fewer than 33 elements, namely subsets with 00, 11, or 22 elements.

To do that, we employ the binomial coefficient (nk)\binom{n}{k}, which counts the number of subsets of size kk from an nn-element set.

We therefore compute:

(80)\binom{8}{0} gives the number of empty subsets, which is 11.

(81)\binom{8}{1} gives the number of single-element subsets, which is 88.

(82)\binom{8}{2} gives the number of two-element subsets. Using the combination formula (n2)=n(n−1)2\binom{n}{2} = \dfrac{n(n-1)}{2}, we obtain

(82)=8×72=28.\binom{8}{2} = \dfrac{8 \times 7}{2} = 28.

Now we add these three quantities to find the total number of subsets that have fewer than three elements:

(80)+(81)+(82)=1+8+28=37.\binom{8}{0} + \binom{8}{1} + \binom{8}{2} = 1 + 8 + 28 = 37.

Finally, we subtract this result from the grand total of 256256 subsets to get the desired count of subsets with at least three elements:

256−37=219.256 - 37 = 219.

Therefore, the number of subsets of A×BA \times B each having at least three elements is 219219.

Hence, the correct answer is Option B.

Tagged Cartesian products and counting relations. Machine-assigned, so read it as a strong shortlist rather than a verdict.

TopicCartesian products and counting relations
TypeMultiple choice