# Number of subsets of $\{1,2,3,\dots,10\}$ with an element divisible by $3$

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 :)

-
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
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

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.$$