Let $X = \{1,2, \ldots ,10\}$. Define 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$.

I'm really not sure how to go about this. Any hints would be greatly appreciated.


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

  • $\begingroup$ 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. $\endgroup$ – Fly by Night Apr 23 '13 at 16:59
  • $\begingroup$ This makes sense. Thanks. $\endgroup$ – 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$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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