0
$\begingroup$

Can someone please explain why the following question's answer is (a)?

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?

(a) 2^35

(b) 2^36

(c) 2^37 − 2^35

(d) 2^35 + 2^36

$\endgroup$
0
$\begingroup$

Think of it this way: Let $S = \left\lbrace s_1,s_2, \ldots, s_{37} \right\rbrace$. Every subset $A \subseteq S$ can be identified by a sequence $$(a_1,a_2, \ldots, a_{37}) ~ , ~ a_i \in \{0,1\}.$$ in the way that $a_i = 1$ if $s_i \in A$ and $a_i =0$ if $s_i \notin A$. Now you know that $x$ is some $s_m$ and $y$ is some $s_n$. If $x$ is in $A$ and $y$ isn't, this means that $a_m = 1$ and $a_n = 0$. However, every other $a_i$ can be either $0$ or $1$. Since there are $35$ other $a_i$'s left, you are looking for the number of sequences of length $35$ using only the symbols $0$ and $1$. This is $$\underbrace{2 \cdot 2 \cdot 2 \cdot \ldots \cdot 2}_{35 \text{ times}} = 2^{35}$$ because at every position you have $2$ symbols to choose from.

$\endgroup$
1
$\begingroup$

There are $2^{|S \setminus \{x,y\}|}=2^{35}$ subsets of $S \setminus \{x,y\}$. We add $x$ to each of them to obtain the $2^{35}$ subsets of $S$ that contain $x$ but don't contain $y$.

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