RankRizz
JEE MAIN 2021 · 27 AUG S2+4HARDTRANSCRIBED

JEE Main 2021 Mathematics question — Combinations and selections with conditions

Let S={1,2,3,4,5,6,9}S = \{1, 2, 3, 4, 5, 6, 9\}. Then the number of elements in the set T={A⊆S:A≠ϕT = \{A \subseteq S : A \neq \phi and the sum of all the elements of AA is not a multiple of 3}\} is _________.

SOLUTION

We have the set S={1,2,3,4,5,6,9}S=\{1,2,3,4,5,6,9\} containing seven elements. For every subset A⊆SA\subseteq S we are interested in the remainder obtained when the sum of its elements is divided by 3. Because divisibility by 3 depends only on the remainder, it is natural to classify each element of SS according to its remainder (or “residue”) modulo 3.

Computing the residues, we obtain

1≡1(mod3),2≡2(mod3),3≡0(mod3),4≡1(mod3),5≡2(mod3),6≡0(mod3),9≡0(mod3).\begin{aligned} 1&\equiv1\pmod3,\\ 2&\equiv2\pmod3,\\ 3&\equiv0\pmod3,\\ 4&\equiv1\pmod3,\\ 5&\equiv2\pmod3,\\ 6&\equiv0\pmod3,\\ 9&\equiv0\pmod3. \end{aligned}

So the seven elements fall into three residue classes:

Class 0:  {3,6,9}⟹n0=3,Class 1:  {1,4}⟹n1=2,Class 2:  {2,5}⟹n2=2.\begin{array}{lcl} \text{Class }0:&\; \{3,6,9\} &\Longrightarrow n_0=3,\\[2pt] \text{Class }1:&\; \{1,4\} &\Longrightarrow n_1=2,\\[2pt] \text{Class }2:&\; \{2,5\} &\Longrightarrow n_2=2. \end{array}

Choosing elements from the “0‐class” never alters the remainder, because each of those numbers is itself a multiple of 3. Hence any subset chosen from {3,6,9}\{3,6,9\} contributes 00 (mod 3) to the total sum. There are 2n0=23=82^{n_0}=2^{3}=8 possible selections from this class, including the empty selection.

If we pick k1k_1 elements from the “1‐class”, each contributes a remainder 11, so their combined remainder is

k1(mod3).k_1\pmod3.

Because n1=2n_1=2, the value k1k_1 may be 0,1,0,1, or 22, and the corresponding numbers of ways are

(20)=1,(21)=2,(22)=1.\binom{2}{0}=1,\quad\binom{2}{1}=2,\quad\binom{2}{2}=1.

Similarly, choosing k2k_2 elements from the “2‐class” gives a combined remainder

2k2(mod3),2k_2\pmod3,

and with n2=2n_2=2 the admissible values and counts are also

(20)=1,(21)=2,(22)=1.\binom{2}{0}=1,\quad\binom{2}{1}=2,\quad\binom{2}{2}=1.

For the total sum of a subset to be a multiple of 3 we require

k1+2k2≡0(mod3).k_1+2k_2\equiv0\pmod3.

We now list every pair (k1,k2)(k_1,k_2) satisfying this condition together with the number of ways it can occur.

1. k1=0k_1=0 gives residue 00. We need 2k2≡0(mod3)2k_2\equiv0\pmod3, which is true only for k2=0k_2=0. Number of ways:

(20)×(20)=1×1=1.\binom{2}{0}\times\binom{2}{0}=1\times1=1.

2. k1=1k_1=1 gives residue 11. We need 1+2k2≡0(mod3)  ⟹  2k2≡2(mod3)  ⟹  k2=1.1+2k_2\equiv0\pmod3\;\Longrightarrow\;2k_2\equiv2\pmod3\;\Longrightarrow\;k_2=1. Number of ways:

(21)×(21)=2×2=4.\binom{2}{1}\times\binom{2}{1}=2\times2=4.

3. k1=2k_1=2 gives residue 22. We need 2+2k2≡0(mod3)  ⟹  2k2≡1(mod3)  ⟹  k2=2.2+2k_2\equiv0\pmod3\;\Longrightarrow\;2k_2\equiv1\pmod3\;\Longrightarrow\;k_2=2. Number of ways:

(22)×(22)=1×1=1.\binom{2}{2}\times\binom{2}{2}=1\times1=1.

Adding these counts, the total number of ways to choose elements from the “1‐class” and “2‐class” so that the running sum is divisible by 3 is

1+4+1=6.1+4+1=6.

For every such choice we may freely choose any subset of the three “0‐class” elements, and there are 88 possibilities for that. Multiplying, the number of all subsets (including the empty one) whose element-sum is a multiple of 3 equals

6×8=48.6\times8=48.

Among these 4848 subsets, one is the empty set itself. Because the problem specifically excludes the empty set (it demands A≠∅A\neq\varnothing), the count of non-empty subsets with sum divisible by 3 is

48−1=47.48-1=47.

The total number of non-empty subsets of a 7-element set is

27−1=128−1=127.2^{7}-1=128-1=127.

Therefore the number of non-empty subsets whose element-sum is not a multiple of 3 is obtained by simple subtraction:

127−47=80.127-47=80.

Hence, the correct answer is Option C (8080).

Tagged Combinations and selections with conditions. Machine-assigned, so read it as a strong shortlist rather than a verdict.

TopicCombinations and selections with conditions
TypeNumerical answer