# Counting the number of subsets of any size.

Let $X = \{1,2, \ldots ,10\}$. Deﬁne the relation $R$ on $X$ by: $\forall a,b \in X, \; aRb$ if and only if $a\cdot b$ is even.

a) Find the number of subsets, $S$ of $X$, of any size that satisfy the following property: $\forall a \in S,\;\exists b \in S$ such that $aRb$.

Call a subset of this type good and all others bad. Note that the only bad subsets are those whose only elements are odd. Thus the number of good subsets is $$|\mathcal{P}(X)|-|\mathcal{P}(\{1,3,5,7,9\})|=2^{10}-2^{5}=992$$ Obviously by $\mathcal{P}(E)$ I mean the power-set of $E$.

• Mathematically, this is a great answer. To make it perfect, please say a few words about what $\mathcal{P}(X)$, etc, means and justify your steps. – Fly by Night Apr 23 '13 at 16:59
• This makes sense. Thanks. – Ian Apr 23 '13 at 17:02

If a subset $S$ contains a single even element $a$, then $ab$ will be even for all $b\in S$.

So essentially what is required is the number of sets which contain at least one even element. Now there are 5 odd numbers in $X$ and 5 even numbers. So the required number is the number of unions of all subsets of the odds of $X$ with all non-empty subsets of the evens. (Since the odds and evens are disjoint there will be no overlap or double-counting problems.)

This value is $2^5\times(2^5-1)=32\times31=992$