0
$\begingroup$

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

$(a) 2^{36} − 2^{34}$

$(b) 2^{36} − 2^{35}$

$(c) 2^{37} − 2^{34}$

$(d) 2^{37} − 2^{35}$

This is a review question, so if someone can help me out it would be appreciated!

Thanks!

$\endgroup$
  • $\begingroup$ What have you tried? Working out the solution when $S$ has size $4$ or $5$ might give you a clue as to how to proceed. $\endgroup$ – ajd Oct 24 '14 at 5:08
1
$\begingroup$

Hints:

The number of subsets of $S$ that does not contain $z$ is the same as the number of subsets of $S-\{z\}$.

The number of subsets of $S$ that contains $x$ or $y$ are all the subsets minus all the subsets of $S-\{x,y\}$.

$\endgroup$
0
$\begingroup$

Let A be the set of subsets of S that contain x but not z, and

let B be the set of subsets of S that contain y but not z.

Then $|A|$ is the number of subsets of $S-\{x,z\}$, and $|B|$ is the number of subsets of $S-\{y,z\}$; so

$|A\cup B|=|A|+|B|-|A\cap B|=2^{35}+2^{35}-2^{34}=2^{36}-2^{34}$

since $|A\cap B|$ is the number of subsets of $S-\{x,y,z\}$.


Alternate solution:

For $\begin{bmatrix}x\\y\\z\end{bmatrix}$, we have 3 choices: $\begin{bmatrix}1\\1\\0\end{bmatrix},\begin{bmatrix}1\\0\\0\end{bmatrix},\begin{bmatrix}0\\1\\0\end{bmatrix}$.

For each of the other 34 elements, there are 2 choices; so there are

$3\cdot2^{34}=(4-1)\cdot2^{34}=2^{36}-2^{34}$ possible subsets.

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