2
$\begingroup$

Let $S$ be a set of size $37$, and let $x$ and $y$ be two distinct elements of $S$. How many subsets of $S$ are there that contain $x$ but do not contain $y$?

This question is on a practice exam that I am reviewing for tomorrow. The answer key says that the answer to this question is $2^{37} - 2^{35}$.

I fail to see how this is correct as $2^{37}$ would be the amount of all subsets and $2^{35}$ is the amount of subsets containing x and y (I believe), therefore the answer would be the # of subsets that do not contain x or y, which doesn't answer the question.

I thought the answer should be $2^{36} - 2^{35}$, where $2^{36}$ is the number of subsets containing $x$, taking away the number of subsets that contain both $x$ and $y$, therefore being left with the number of subsets that contain $x$ and not $y$.

Can someone please confirm that I am right or explain to me why I am wrong?

$\endgroup$
  • 3
    $\begingroup$ You are correct, the number of such subsets is $2^{36}-2^{35}$ or simply $2^{35}$. The answer key is just wrong, assuming the problem is quoted correctly above. $\endgroup$ – hardmath Apr 16 '15 at 16:00
2
$\begingroup$

You are correct; the answer should be $2^{36}-2^{35}=2^{35}$.

Another way of looking at it: $x$ must be in any such subset, and $y$ must not be. Thus, we have $35$ "free" elements that could either be in or out of the subset. So, there are $2^{35}$ ways of forming that subset.

$\endgroup$

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.