Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have a question which is:

Given the set {1,2,3,4,5,6,7,8,9,10}. Calculate the number of subsets having an element divisible by 3.

I got the answer 896 by subtracting the number of subsets of the set without 3,6,9 from the number of subsets of the full set IE: 1024 - 128.

But I have a feeling this is incorrect. If so can someone correct me and explain why?

Thanks :)

share|improve this question
    
Dear OP, I changed your title so that it more accurately represents your problem, as opposed to a distinct but similarly worded one asked by Qiaochu. –  anon Aug 20 '11 at 6:19
2  
Clear compact argument. Minor typo, $1024-128$ is not $89$. Another minor typo, the the the. –  André Nicolas Aug 20 '11 at 6:23
    
Thanks, fixed now –  Jason Aug 20 '11 at 9:05

1 Answer 1

up vote 4 down vote accepted

Split the set into $A=\{1,2,4,5,7,8,10\}$ and $B=\{3,6,9\}$. Subsets of $A\cup B$ that have at least one element divisible by $3$ will have one or more elements of $B$ and any number of elements of $A$, and these selections are independent of each other. Thus we have

$$ = |\mathcal{P}(A)|\times (|\mathcal{P}(B)|-1)= 2^7(2^3-1)=896.$$

(We subtracted $1$ above to rule out the empty set, which corresponds to no multiples of $3$ in our sets.) Alternatively we can use your method, which is a bit slicker. This is

$$|\mathcal{P}(A\cup B)|-|\mathcal{P(A)|}=2^{10}-2^7=896.$$

EDIT: Actually, it seems your only problem (pointed out by André in the comments) is you didn't do the subtraction correctly. But your reasoning is sound.

share|improve this answer
    
Great Thanks, Fixed the typo now :) –  Jason Aug 20 '11 at 9:01

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.