Permutations & Combinations
Subsets with sum divisible by 3
nta_pyq_2023_jan
Grade 11
Question:
Let S = {1, 2, 3, 5, 7, 10, 11}. The number of non-empty subsets of S that have the sum of all elements a multiple of 3, is ____.
Step-by-Step Solution
Key Concept: Classify elements by residue mod 3: type 3k, type 3k+1, type 3k+2. Count subsets where total residue ≡ 0 (mod 3).
Elements: 3k={3}, 3k+1={1,7,10}, 3k+2={2,5,11}. Counting subsets of each size with sum divisible by 3: S₁=1, S₂=9, S₃=11, S₄=11, S₅=9, S₆=1, S₇=1. Sum = 43.
Correct Answer: 43