2
$\begingroup$

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

  • 2
    Clear compact argument. Minor typo, $1024-128$ is not $89$. Another minor typo, the the the.2011-08-20

1 Answers 1

4

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.

  • 0
    Great Thanks, Fixed the typo now :)2011-08-20