RankRizz
JEE MAIN 2019 · 12 JAN S1+4 / −1MEDIUMTRANSCRIBED

JEE Main 2019 Mathematics question — Cartesian products and counting relations

Let S={1,2,3,…,100}S = \{1, 2, 3, \ldots, 100\}, then number of non-empty subsets A of S such that the product of elements in A is even is:

SOLUTION

First, recall the basic counting fact: if a finite set has nn elements, the total number of all its subsets (including the empty set) is 2 n2^{\,n}, because each element may be either “chosen” or “not chosen”.

Here the set is S={1,2,3,…,100}S=\{1,2,3,\ldots ,100\}, so ∣S∣=100|S| = 100. Hence, by the above fact, the total number of subsets of SS is 21002^{100}. Among these, exactly one subset is empty, so the number of non-empty subsets is

2100−1.2^{100}-1.

We are asked to count those non-empty subsets AA whose product of elements is even. A product of integers is even as soon as at least one factor is even. Therefore a subset has an even product precisely when it contains at least one even number. The complementary situation is that the subset contains no even numbers at all, i.e. it is formed entirely of odd numbers; such a subset will clearly have an odd product.

So, instead of counting the “even-product” subsets directly, we count all non-empty subsets and subtract the non-empty subsets that consist only of odd numbers. This is the classic “complement counting” technique.

Among the first 100 positive integers, exactly half are odd and half are even, because the list alternates parity. Concretely, the odd numbers are

1,3,5,…,99,1,3,5,\ldots ,99,

and there are 5050 of them. Let us call this set of odd numbers OO, so ∣O∣=50|O| = 50.

Applying again the subset-counting fact, the total number of subsets of OO (including the empty subset) is 2502^{50}. Excluding the empty subset, the number of non-empty subsets of OO is therefore

250−1.2^{50}-1.

Every such subset uses only odd elements, hence its product is odd. Consequently, the count 250−12^{50}-1 is exactly the number of non-empty subsets of SS having an odd product.

Now we subtract these from the total number of non-empty subsets to obtain the desired count of even-product subsets:

Number of even-product subsets=(2100−1)  −  (250−1)=2100−1−250+1=2100−250.\begin{aligned} \text{Number of even-product subsets} &= (2^{100}-1) \;-\; (2^{50}-1)\\[4pt] &= 2^{100}-1-2^{50}+1\\[4pt] &= 2^{100}-2^{50}.\\ \end{aligned}

This difference can be factorised by taking 2502^{50} common:

2100−250=250(2100−50−1)=250(250−1).2^{100}-2^{50} = 2^{50}\left(2^{100-50}-1\right) = 2^{50}\left(2^{50}-1\right).

Thus the number of non-empty subsets of SS whose product is even is 250(250−1)2^{50}\bigl(2^{50}-1\bigr).

Looking at the given options, this expression matches Option C.

Hence, the correct answer is Option C.

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