Explanation
Solution
Step 1: Elements ko remainder ke basis par group karna
Set S={1,2,3,5,7,10,11} ke elements ko 3 se divide karne par milne waale remainders ke hisaab se distribute karte hain:
-
Type R0 (Remainder 0): {3} → (1 element)
-
Type R1 (Remainder 1): {1,7,10} → (3 elements)
-
Type R2 (Remainder 2): {2,5,11} → (3 elements)
Step 2: Generating Function ka upyog
Subset ka sum 3 ka multiple hone ke liye hum complex roots of unity (ω) ka upyog karte hain:
P(x)=(1+x3)(1+x1+x7+x10)(1+x2+x5+x11)
Power ko mod 3 mein badalne par:
P(ω)=(1+ω0)1⋅(1+ω1)3⋅(1+ω2)3
Hume pata hai ki (1+ω)=−ω2 aur (1+ω2)=−ω:
Step 3: Subsets ki sankhya nikalna
Multiple of 3 waale subsets ka formula:
Yahan:
Step 4: Non-empty condition apply karna
Kyonki question mein non-empty subset pucha gaya hai, hum empty set (jiska sum 0 hota hai aur 0 bhi 3 ka multiple hai) ko subtract karenge:
