Solution: 2017 Fall Midterm - 5

Author: Michiel Smid

Question

Let $n \geq 2$ be an even integer and let $S = \{1,2,3,\dots,n\}$. Consider subsets of $S$ that contain at least one even number. How many such subsets are there?

(a)

$2^{n/2} + 2^{n/2}$

(b)

$2^{n} + 2^{n/2}$

(c)

$2^{n} - 2^{n/2}$

(d)

$(n/2) \cdot 2^{n/2}$

Solution

$ |S| = 2^n $

B = subsets that contain no even numbers.

Since it’s incremental, we know half the values are odd and half are even.

That means there are a total of $ 2^{ \frac{n}{2}} $ subsets that contain no even numbers.

$ |B| = 2^{ \frac{n}{2}} $

A = subsets that contain at least one even number.

$ |A| = 2^n - |B| $

$ |A| = 2^n - 2^{ \frac{n}{2}} $