RankRizz
JEE MAIN 2023 · 25 JAN S1+4 / −1HARDTRANSCRIBED

JEE Main 2023 Mathematics question — Cartesian products and counting relations

Let S={1,2,3,5,7,10,11}S = \{1, 2, 3, 5, 7, 10, 11\}. The number of non-empty subsets of SS that have the sum of all elements a multiple of 3, is _____.

SOLUTION

We need to find the number of non-empty subsets of S={1,2,3,5,7,10,11}S = \{1, 2, 3, 5, 7, 10, 11\} whose element sum is a multiple of 3.

  • Residue 0: {3}\{3\} — 1 element
  • Residue 1: {1,7,10}\{1, 7, 10\} — 3 elements
  • Residue 2: {2,5,11}\{2, 5, 11\} — 3 elements

Residue 0 group {3}\{3\}: Including or excluding 3 does not affect the sum mod 3. So this element provides a factor of 2 (include or exclude).

Residue 1 group {1,7,10}\{1, 7, 10\}: Each subset of this group has a sum with some residue mod 3. There are 23=82^3 = 8 subsets (including empty).

  • Sum ≡0\equiv 0: ∅\emptyset (sum 0), {1,7,10}\{1, 7, 10\} (sum 18) — 2 subsets
  • Sum ≡1\equiv 1: {1}\{1\} (1), {7}\{7\} (7), {10}\{10\} (10) — 3 subsets
  • Sum ≡2\equiv 2: {1,7}\{1,7\} (8), {1,10}\{1,10\} (11), {7,10}\{7,10\} (17) — 3 subsets

Residue 2 group {2,5,11}\{2, 5, 11\}: Similarly, 23=82^3 = 8 subsets.

  • Sum ≡0\equiv 0: ∅\emptyset (sum 0), {2,5,11}\{2, 5, 11\} (sum 18) — 2 subsets
  • Sum ≡1\equiv 1: {2,5}\{2, 5\} (7), {2,11}\{2, 11\} (13), {5,11}\{5, 11\} (16) — 3 subsets
  • Sum ≡2\equiv 2: {2}\{2\} (2), {5}\{5\} (5), {11}\{11\} (11) — 3 subsets

For the total sum to be ≡0(mod3)\equiv 0 \pmod{3}, the contributions from residue-1 and residue-2 groups must satisfy:

r1+r2≡0(mod3)r_1 + r_2 \equiv 0 \pmod{3}

Valid combinations (r1,r2)(r_1, r_2):

  • (0,0)(0, 0): 2×2=42 \times 2 = 4 subsets
  • (1,2)(1, 2): 3×3=93 \times 3 = 9 subsets
  • (2,1)(2, 1): 3×3=93 \times 3 = 9 subsets

Total from residue 1 and 2 groups = 4+9+9=224 + 9 + 9 = 22 subsets.

Element 3 can be included or excluded without affecting divisibility by 3:

22×2=44 subsets (including empty set)22 \times 2 = 44 \text{ subsets (including empty set)}

44−1=4344 - 1 = 43

The answer is 4343.

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

TopicCartesian products and counting relations
TypeNumerical answer